Submission #1127570
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct cww{cww(){
ios::sync_with_stdio(false);cin.tie(0);
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
template <typename T>inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>inline void chmax(T &l,T r){l=max(l,r);}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
for(auto &it:v)is>>it;
return is;
}
namespace _DSU{
int cnt=0;
int mem[2][212345];
int* get(){
return mem[cnt++];
}
}
LL res[112345];
int S[112345];
int T[112345];
set<int> query[41234];
int task[112345];
class UnionFind{
private:
int *par,*rank;
int find(int x){
if (par[x] == x) return x;
else return par[x] = find(par[x]);
}
public:
UnionFind(int n,int *par,int *rank) :par(par),rank(rank){
for(int i = 0; i < n; i++)par[i] = i,rank[i] = 0;
}
UnionFind(int n):UnionFind(n,_DSU::get(),_DSU::get()){}
int unite(int x, int y){
x = find(x);y = find(y);
if (x == y)return -1;
int sz=0;
if(query[x].size()>query[y].size())swap(x,y);
for(auto &it:query[x]){
if(query[y].count(it)){
task[sz++]=it;
query[y].erase(it);
}
else query[y].insert(it);
}
query[x].clear();
if (rank[x] < rank[y])swap(x,y);
if(query[x].size()==0)swap(query[x],query[y]);
par[y] = x;
if (rank[x] == rank[y])rank[x]++;
return sz;
}
bool same(int x, int y){
return find(x) == find(y);
}
};
typedef tuple<LL,int,int> E;
int main(){
int N,M,Q;
cin>>N>>M;
vector<E> e(M);
REP(i,M){
int s,t;LL c;
cin>>s>>t>>c;
e[i]=E(c,s,t);
}
sort(e.begin(),e.end());
cin>>Q;
REP(i,Q){
cin>>S[i]>>T[i];
query[S[i]].insert(i);
query[T[i]].insert(i);
}
LL cost=0;
UnionFind uf(N+1);
REP(i,M){
int a,b;LL c;
tie(c,a,b)=(e[i]);
int k=uf.unite(a,b);
if(k==-1)continue;
REP(i,k){
res[task[i]]=c;
}
cost+=c;
}
REP(i,Q)cout<<cost-res[i]<<fin;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
btk15049 |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2453 Byte |
Status |
AC |
Exec Time |
346 ms |
Memory |
21120 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
200 / 200 |
300 / 300 |
200 / 200 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_1.txt, sample_2.txt |
subtask1 |
sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 |
sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt |
All |
sample_1.txt, sample_2.txt, sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_1.txt |
AC |
2 ms |
3968 KB |
sample_2.txt |
AC |
3 ms |
3968 KB |
subtask_1_1.txt |
AC |
3 ms |
4096 KB |
subtask_1_10.txt |
AC |
68 ms |
7040 KB |
subtask_1_11.txt |
AC |
3 ms |
3968 KB |
subtask_1_2.txt |
AC |
16 ms |
4608 KB |
subtask_1_3.txt |
AC |
135 ms |
10240 KB |
subtask_1_4.txt |
AC |
4 ms |
3968 KB |
subtask_1_5.txt |
AC |
4 ms |
4096 KB |
subtask_1_6.txt |
AC |
35 ms |
5504 KB |
subtask_1_7.txt |
AC |
135 ms |
10240 KB |
subtask_1_8.txt |
AC |
4 ms |
3968 KB |
subtask_1_9.txt |
AC |
6 ms |
4096 KB |
subtask_2_1.txt |
AC |
138 ms |
10496 KB |
subtask_2_2.txt |
AC |
138 ms |
10496 KB |
subtask_2_3.txt |
AC |
138 ms |
10496 KB |
subtask_2_4.txt |
AC |
140 ms |
10496 KB |
subtask_2_5.txt |
AC |
7 ms |
4352 KB |
subtask_2_6.txt |
AC |
12 ms |
4608 KB |
subtask_2_7.txt |
AC |
39 ms |
5888 KB |
subtask_2_8.txt |
AC |
144 ms |
10496 KB |
subtask_3_1.txt |
AC |
346 ms |
20992 KB |
subtask_3_2.txt |
AC |
330 ms |
21120 KB |
subtask_3_3.txt |
AC |
269 ms |
14976 KB |
subtask_3_4.txt |
AC |
196 ms |
14848 KB |
subtask_3_5.txt |
AC |
261 ms |
17792 KB |
subtask_3_6.txt |
AC |
328 ms |
19456 KB |
subtask_3_7.txt |
AC |
345 ms |
20992 KB |
subtask_3_8.txt |
AC |
345 ms |
20864 KB |