Submission #828585
Source Code Expand
#include "grader.h"
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <set>
#define SIZE 100005
#define INF 1000000005
#define SQR 200
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
struct UF
{
int par[SIZE],rank[SIZE];
void init(int n)
{
for(int i=0;i<n;i++)
{
par[i]=i;
rank[i]=0;
}
}
int find(int x)
{
if(par[x]==x) return x;
return par[x]=find(par[x]);
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y) return;
if(rank[x]<rank[y])
{
par[x]=y;
}
else
{
par[y]=x;
if(rank[x]==rank[y]) rank[x]++;
}
}
bool same(int x,int y)
{
return find(x)==find(y);
}
};
struct UF2
{
int par[SIZE],rank[SIZE];
int rep[SIZE];
void init(int n)
{
for(int i=0;i<n;i++)
{
par[i]=i;
rank[i]=0;
rep[i]=-1;
}
}
void ins(int k,int x)
{
rep[k]=x;
}
int find(int x)
{
if(par[x]==x) return x;
return par[x]=find(par[x]);
}
P unite(int x,int y)
{
P ret=P(-1,-1);
x=find(x);
y=find(y);
if(x==y) return ret;
ret.second=0;
if(rep[x]!=-1&&rep[y]!=-1) ret=P(rep[x],rep[y]);
if(rank[x]<rank[y])
{
par[x]=y;
rep[y]=max(rep[x],rep[y]);
}
else
{
par[y]=x;
rep[x]=max(rep[x],rep[y]);
if(rank[x]==rank[y]) rank[x]++;
}
return ret;
}
bool same(int x,int y)
{
return find(x)==find(y);
}
};
UF uf[SQR];
UF2 cmb;
vector <P> vec[SIZE];
vector <PP> edge;
bool use[SIZE];
int id[SIZE];
ll ans[SIZE];
int n;
void solve(int k)
{
int l=k*SQR,r=min((k+1)*SQR,n);
memset(use,false,sizeof(use));
vector <PP> now;
for(int i=l;i<r;i++)
{
use[i]=true;
for(int j=0;j<vec[i].size();j++)
{
int to=vec[i][j].first;
if(to<l) use[to]=true;
now.push_back(PP(vec[i][j].second,P(to,i)));
}
}
memset(id,-1,sizeof(id));
int sz=0;
for(int i=0;i<r;i++) if(use[i]) id[i]=sz++;
int all=r-l;
for(int i=0;i<all;i++) uf[i].init(sz+2);
cmb.init(l+2);
for(int i=0;i<l;i++) if(use[i]) cmb.ins(i,i);
sort(now.begin(),now.end());
vector <PP> nxt;
int lp=0,rp=0;
while(lp<edge.size()||rp<now.size())
{
if(rp==now.size()||(lp<edge.size()&&edge[lp]<now[rp])) nxt.push_back(edge[lp++]);
else nxt.push_back(now[rp++]);
}
edge=nxt;
//printf("%d : ",sz);
//for(int i=0;i<n;i++) printf("%d ",id[i]);puts("");
ll pl=0;
for(int i=0;i<edge.size();i++)
{
int s=edge[i].second.first,t=edge[i].second.second;
if(t<l)
{
P p=cmb.unite(s,t);
if(p.first!=-1)
{
int a=id[p.first],b=id[p.second];
//if(k==2) printf("%d %d %d : %d %d\n",edge[i].first,s,t,a,b);
for(int j=0;j<all;j++)
{
if(!uf[j].same(a,b))
{
ans[j+l]+=edge[i].first;
uf[j].unite(a,b);
}
}
}
else if(p.second==0) pl+=edge[i].first;
}
else
{
int start=t-l;
int a=id[s],b=id[t];
//printf("%d : %d %d\n",start,a,b);
for(int j=start;j<all;j++)
{
if(!uf[j].same(a,b))
{
ans[j+l]+=edge[i].first;
uf[j].unite(a,b);
}
}
}
}
bool up=true;
for(int i=0;i<l;i++) if(cmb.rep[cmb.find(i)]==-1) up=false;
for(int i=l;i<r;i++)
{
//valid check
bool ok=up;
int nm=(sz-all)+(i-l+1);
for(int j=1;j<nm;j++)
{
if(!uf[i-l].same(0,j))
{
ok=false;
break;
}
}
if(!ok) ans[i]=-1;
else ans[i]+=pl;
}
}
void construct(int N, int M, int E[][3])
{
memset(ans,0,sizeof(ans));
n=N;
for(int i=0;i<M;i++) vec[E[i][1]].push_back(P(E[i][0],E[i][2]));
for(int i=0;i<=(n-1)/SQR;i++) solve(i);
for(int i=1;i<n;i++) answer(ans[i]);
}/*
int N;
int M;
int E[SIZE][3];
int main()
{
scanf("%d %d",&N,&M);
for(int i=0;i<M;i++) scanf("%d %d %d",&E[i][0],&E[i][1],&E[i][2]);
construct(N,M,E);
for(int i=1;i<N;i++) printf("%lld ",ans[i]);
puts("");
return 0;
}*/
Submission Info
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Subtask3 |
Subtask4 |
Score / Max Score |
16 / 16 |
24 / 24 |
59 / 59 |
0 / 1 |
Status |
|
|
|
|
Set Name |
Test Cases |
Subtask1 |
subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9 |
Subtask2 |
subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9, subtask2/1, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6 |
Subtask3 |
subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9, subtask2/1, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6, subtask3/1, subtask3/2, subtask3/3, subtask3/4, subtask3/5 |
Subtask4 |
subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9, subtask2/1, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6, subtask3/1, subtask3/2, subtask3/3, subtask3/4, subtask3/5, subtask4/1, subtask4/2, subtask4/3, subtask4/4, subtask4/5 |
Case Name |
Status |
Exec Time |
Memory |
subtask1/1 |
AC |
33 ms |
4376 KB |
subtask1/2 |
AC |
33 ms |
4384 KB |
subtask1/3 |
AC |
31 ms |
4512 KB |
subtask1/4 |
AC |
31 ms |
4340 KB |
subtask1/5 |
AC |
52 ms |
6820 KB |
subtask1/6 |
AC |
55 ms |
7072 KB |
subtask1/7 |
AC |
42 ms |
6432 KB |
subtask1/8 |
AC |
41 ms |
6444 KB |
subtask1/9 |
AC |
52 ms |
7200 KB |
subtask2/1 |
AC |
953 ms |
15396 KB |
subtask2/2 |
AC |
928 ms |
15404 KB |
subtask2/3 |
AC |
246 ms |
10884 KB |
subtask2/4 |
AC |
190 ms |
10792 KB |
subtask2/5 |
AC |
1010 ms |
15560 KB |
subtask2/6 |
AC |
72 ms |
7832 KB |
subtask3/1 |
AC |
973 ms |
12516 KB |
subtask3/2 |
AC |
1125 ms |
12876 KB |
subtask3/3 |
AC |
507 ms |
11400 KB |
subtask3/4 |
AC |
373 ms |
11432 KB |
subtask3/5 |
AC |
1052 ms |
13112 KB |
subtask4/1 |
TLE |
1538 ms |
18072 KB |
subtask4/2 |
TLE |
1536 ms |
17712 KB |
subtask4/3 |
TLE |
1536 ms |
18112 KB |
subtask4/4 |
TLE |
1537 ms |
19340 KB |
subtask4/5 |
TLE |
1537 ms |
17676 KB |