Submission #996348
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------
int N,M;
int A[404040],B[404040],C[404040];
vector<pair<int,int>> E[4040];
int Q;
int S[404040],T[404040];
ll D[4040][4040];
template<int um> class UF {
public:
vector<int> par,rank;
UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
int operator()(int x,int y) {
if((x=operator[](x))==(y=operator[](y))) return x;
if(rank[x]>rank[y]) return par[x]=y;
rank[x]+=rank[x]==rank[y]; return par[y]=x;
}
};
UF<5000> uf;
void solve() {
int i,j,k,l,r,x,y; string s;
cin>>N>>M;
priority_queue<pair<int,int>> EE;
FOR(i,M) {
cin>>A[i]>>B[i]>>C[i], A[i]--, B[i]--;
E[A[i]].push_back({B[i],C[i]});
E[B[i]].push_back({A[i],C[i]});
EE.push({-C[i],i});
}
FOR(x,N) FOR(y,N) D[x][y]=(x==y)?0:(1LL<<60);
cin>>Q;
FOR(i,Q) cin>>S[i]>>T[i], S[i]--, T[i]--;
if(Q>1) return;
uf(S[0],T[0]);
ll tot=0;
while(EE.size()) {
auto e=EE.top();
EE.pop();
if(uf[A[e.second]]!=uf[B[e.second]]) {
tot+=-e.first;
uf(A[e.second],B[e.second]);
}
}
cout<<tot<<endl;
}
int main(int argc,char** argv){
string s;int i;
if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
FOR(i,argc-1) s+=argv[i+1],s+='\n';
FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
solve(); return 0;
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
kmjp |
Language |
C++14 (GCC 5.4.1) |
Score |
200 |
Code Size |
1823 Byte |
Status |
WA |
Exec Time |
346 ms |
Memory |
144108 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
200 / 200 |
0 / 300 |
0 / 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 |
WA |
3 ms |
512 KB |
sample_2.txt |
AC |
3 ms |
512 KB |
subtask_1_1.txt |
AC |
4 ms |
896 KB |
subtask_1_10.txt |
AC |
231 ms |
135024 KB |
subtask_1_11.txt |
AC |
3 ms |
384 KB |
subtask_1_2.txt |
AC |
150 ms |
128504 KB |
subtask_1_3.txt |
AC |
343 ms |
143212 KB |
subtask_1_4.txt |
AC |
131 ms |
126848 KB |
subtask_1_5.txt |
AC |
132 ms |
126976 KB |
subtask_1_6.txt |
AC |
180 ms |
130932 KB |
subtask_1_7.txt |
AC |
346 ms |
143340 KB |
subtask_1_8.txt |
AC |
131 ms |
126976 KB |
subtask_1_9.txt |
AC |
134 ms |
127232 KB |
subtask_2_1.txt |
WA |
281 ms |
143340 KB |
subtask_2_2.txt |
WA |
280 ms |
143340 KB |
subtask_2_3.txt |
WA |
280 ms |
143340 KB |
subtask_2_4.txt |
WA |
281 ms |
143340 KB |
subtask_2_5.txt |
WA |
131 ms |
126976 KB |
subtask_2_6.txt |
WA |
138 ms |
127740 KB |
subtask_2_7.txt |
WA |
168 ms |
130932 KB |
subtask_2_8.txt |
WA |
281 ms |
143340 KB |
subtask_3_1.txt |
WA |
294 ms |
143980 KB |
subtask_3_2.txt |
WA |
294 ms |
144108 KB |
subtask_3_3.txt |
WA |
145 ms |
127744 KB |
subtask_3_4.txt |
WA |
148 ms |
128000 KB |
subtask_3_5.txt |
WA |
221 ms |
135792 KB |
subtask_3_6.txt |
WA |
260 ms |
141932 KB |
subtask_3_7.txt |
WA |
296 ms |
144108 KB |
subtask_3_8.txt |
WA |
295 ms |
144108 KB |