Submission #994278
Source Code Expand
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
const int MQ=200000;
const int MN=200000;
int N,Q;
int its[MQ],a[MQ],b[MQ];
int nouse[MQ];
bool e[MQ];
typedef pair<ll,int> P; //cost,id
priority_queue<P,vector<P>,greater<P> > que;
struct unionfind{
int par[MN];
void init(int N){rep(i,N) par[i]=i;}
int find(int x){
if(par[x]==x) return x;
return par[x]=find(par[x]);
}
bool same(int x,int y){
return find(x)==find(y);
}
void unite(int x,int y){
x=find(x),y=find(y);
if(x==y) return;
par[y]=x;
}
}UF;
void iter(int id){
if(!e[id]){
a[id]++;
if(a[id]==N) a[id]=0;
}else{
b[id]++;
if(b[id]==N) b[id]=0;
}
e[id]^=1;
}
int main(){
cin>>N>>Q;
UF.init(N);
rep(i,Q){
ll c;
cin>>a[i]>>b[i]>>c;
que.push(P(c,i));
}
int tm=0;
ll ans=0;
while(tm!=N-1){
P p=que.top();que.pop();
int id=p.sc;
ll c=p.fs;
if(a[id]==b[id]){
// printf("continue id=%d %d,%d\n",id,a[id],b[id]);
iter(id);
que.push(P(c+1,id));
}else if(UF.same(a[id],b[id])){
// printf("no use id=%d %d,%d\n",id,a[id],b[id]);
nouse[id]++;
iter(id);
if(que.size()<=10||nouse[id]<=10) que.push(P(c+1,id));
continue;
}else{
UF.unite(a[id],b[id]);
tm++;
// printf("unite id=%d %d,%d\n",id,a[id],b[id]);
ans+=c;
iter(id);
que.push(P(c+1,id));
}
}
cout<<ans<<endl;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
sigma425 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1978 Byte |
Status |
WA |
Exec Time |
803 ms |
Memory |
6892 KB |
Judge Result
Set Name |
sample |
all |
Score / Max Score |
0 / 0 |
0 / 1300 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt, sample-03.txt |
all |
sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
3 ms |
256 KB |
01-02.txt |
AC |
231 ms |
5488 KB |
01-03.txt |
WA |
455 ms |
6892 KB |
01-04.txt |
AC |
9 ms |
1664 KB |
01-05.txt |
AC |
14 ms |
1408 KB |
01-06.txt |
AC |
18 ms |
1280 KB |
01-07.txt |
WA |
32 ms |
1152 KB |
01-08.txt |
WA |
35 ms |
1152 KB |
01-09.txt |
WA |
81 ms |
1536 KB |
01-10.txt |
WA |
318 ms |
3952 KB |
01-11.txt |
WA |
389 ms |
6380 KB |
01-12.txt |
WA |
548 ms |
6764 KB |
01-13.txt |
WA |
534 ms |
6764 KB |
01-14.txt |
WA |
513 ms |
6764 KB |
01-15.txt |
WA |
579 ms |
6764 KB |
01-16.txt |
WA |
565 ms |
6764 KB |
01-17.txt |
WA |
532 ms |
6764 KB |
01-18.txt |
AC |
803 ms |
6764 KB |
01-19.txt |
AC |
23 ms |
1152 KB |
01-20.txt |
WA |
86 ms |
1152 KB |
01-21.txt |
WA |
203 ms |
2804 KB |
01-22.txt |
AC |
451 ms |
6892 KB |
01-23.txt |
AC |
459 ms |
6764 KB |
01-24.txt |
AC |
169 ms |
1536 KB |
01-25.txt |
AC |
617 ms |
6764 KB |
01-26.txt |
AC |
12 ms |
1024 KB |
01-27.txt |
WA |
132 ms |
1536 KB |
01-28.txt |
AC |
480 ms |
4720 KB |
01-29.txt |
AC |
641 ms |
6508 KB |
01-30.txt |
AC |
712 ms |
6764 KB |
sample-01.txt |
AC |
3 ms |
256 KB |
sample-02.txt |
AC |
3 ms |
256 KB |
sample-03.txt |
AC |
3 ms |
256 KB |