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

Submission Time
Task A - かえってきたどうぶつたち と しんりんのさいせい (Return of Animals and Regeneration of Forests)
User yutaka1999
Language IOI-Style C++ (GCC 5.4.1)
Score 99
Code Size 3974 Byte
Status TLE
Exec Time 1538 ms
Memory 19340 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 16 / 16 24 / 24 59 / 59 0 / 1
Status
AC × 9
AC × 15
AC × 20
AC × 20
TLE × 5
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