Submission #1046916
Source Code Expand
#include<iostream> #include<string> #include<vector> #include<queue> #include<map> #include<algorithm> #include<cmath> #include<set> using namespace std; typedef pair<int64_t,int64_t> P; typedef pair<int64_t,P> T; vector<P> G[4001]; int64_t ans[4001][4001]={}; class uft {//union-find tree public: int parent[4010]; int size[4010]; int root(int x); bool same(int x,int y); void unite(int x,int y); }; int uft::root(int x){ if(parent[x]==x){ return x; } return parent[x] = root(parent[x]); } bool uft::same(int x,int y){ if(root(x)==root(y)){ return true; }else{ return false; } } void uft::unite(int x,int y){ x=root(x); y=root(y); if(x == y) return; parent[x] = y; size[y] = size[y]+size[x]; } int64_t Kruskal(priority_queue<T, vector<T>, greater<T> > q,int N){ uft u; for(int i=0;i<N;i++){ u.parent[i]=i; u.size[i]=1; } int64_t ret=0; while(u.size[u.root(0)] != N && !q.empty()){ T edge = q.top(); q.pop(); int s=(edge.second).first; int t=(edge.second).second; if(u.root(s) != u.root(t) ){ u.unite(s,t); ret += edge.first; G[s].push_back(P(t,edge.first)); G[t].push_back(P(s,edge.first)); //cout<<s<<' '<<t<<' '<<edge.first<<endl; } } return ret; } int main(){ int N,M; cin>>N>>M; priority_queue<T, vector<T>, greater<T> > q; for(int i=0;i<M;i++){ int a,b; int64_t c; cin>>a>>b>>c; a--; b--; T d = T(c,P(a,b)); q.push(d); } int64_t an=Kruskal(q,N); //cout<<an<<endl; for(int i=0;i<N;i++){ bool used[4010]={}; used[i]=true; queue<P> qu; qu.push(P(i,0)); while (!qu.empty()) { P v = qu.front(); qu.pop(); //cout<< v.first <<' '<< v.second <<endl; for(int j=0;j<G[v.first].size();j++){ P u = G[v.first][j]; if(!used[u.first]){ //cout<<v.first<<' '<<v.second<<' '<<u.first<<' '<<u.second<<endl; used[u.first]=true; ans[i][u.first]=max(v.second,u.second); //cout<<"ans "<<i<<' '<<u.first<<' '<<ans[i][u.first]<<endl;cout<<endl; qu.push(P(u.first,ans[i][u.first])); } } } }/* for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ cout<<ans[i][j]<<' '; }cout<<endl; }*/ int Q; cin>>Q; for(int i=0;i<Q;i++){ int s,t; cin>>s>>t; s--;t--; cout<< an - ans[s][t] << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Graph |
User | cocococoa |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 2841 Byte |
Status | AC |
Exec Time | 1495 ms |
Memory | 136136 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, 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 | 3 ms | 384 KB |
sample_2.txt | AC | 3 ms | 384 KB |
subtask_1_1.txt | AC | 4 ms | 896 KB |
subtask_1_10.txt | AC | 778 ms | 130332 KB |
subtask_1_11.txt | AC | 3 ms | 384 KB |
subtask_1_2.txt | AC | 634 ms | 126536 KB |
subtask_1_3.txt | AC | 977 ms | 134984 KB |
subtask_1_4.txt | AC | 617 ms | 125824 KB |
subtask_1_5.txt | AC | 608 ms | 125888 KB |
subtask_1_6.txt | AC | 682 ms | 127944 KB |
subtask_1_7.txt | AC | 972 ms | 134984 KB |
subtask_1_8.txt | AC | 612 ms | 125824 KB |
subtask_1_9.txt | AC | 599 ms | 125840 KB |
subtask_2_1.txt | AC | 984 ms | 134984 KB |
subtask_2_2.txt | AC | 984 ms | 134984 KB |
subtask_2_3.txt | AC | 983 ms | 134984 KB |
subtask_2_4.txt | AC | 993 ms | 134984 KB |
subtask_2_5.txt | AC | 627 ms | 125824 KB |
subtask_2_6.txt | AC | 626 ms | 126112 KB |
subtask_2_7.txt | AC | 701 ms | 127944 KB |
subtask_2_8.txt | AC | 986 ms | 134984 KB |
subtask_3_1.txt | AC | 1453 ms | 136136 KB |
subtask_3_2.txt | AC | 1495 ms | 136136 KB |
subtask_3_3.txt | AC | 1100 ms | 127232 KB |
subtask_3_4.txt | AC | 1093 ms | 127120 KB |
subtask_3_5.txt | AC | 1267 ms | 131484 KB |
subtask_3_6.txt | AC | 1369 ms | 133872 KB |
subtask_3_7.txt | AC | 1462 ms | 136136 KB |
subtask_3_8.txt | AC | 1464 ms | 136136 KB |