Submission #116585

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116585	2019-06-13T03:14:00 Z	faustaadp	Parachute rings (IOI12_rings)	C++17	20 / 100	4000 ms	78588 KB

rings

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,isi[1010101],D[1010101],i,j,CC;
vector<ll> v[1010101];
vector<ll> w[1010101];
ll br[1010101],tot;
ll mi[1010101];
ll b[1010101];
ll p[1010101];
ll nw[1010101],te,Z,has;
void Init(int N_) {
  n = N_;
  CC=n;
  isi[0]=n;
  for(i=1;i<=n;i++)p[i]=i;
  memset(b,-1,sizeof(b));
  memset(br,-1,sizeof(br));
}
ll car(ll aa)
{
	if(p[aa]==aa)
		return aa;
	else 
		return p[aa]=car(p[aa]);
}
void dfs(ll aa,ll bb)
{
	te++;
	nw[aa]=te;
	mi[aa]=te;
	b[aa]=Z;
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
	{
		if(v[aa][ii]==bb)continue;
		if(b[v[aa][ii]]!=Z)
		{
			dfs(v[aa][ii],aa);
			mi[aa]=min(mi[aa],mi[v[aa][ii]]);
		}
		else
			mi[aa]=min(mi[aa],nw[v[aa][ii]]);
		if(mi[v[aa][ii]]>nw[aa])
			br[w[aa][ii]]=Z;
	}
}
void Link(int A, int B) 
{
	Z++;
	v[A].pb(B);
	w[A].pb(Z);
	v[B].pb(A);
	w[B].pb(Z);
	if(p[car(A)]!=car(B))
	{
		p[car(A)]=car(B);
		CC--;
	}
	D[A]++;
	D[B]++;
	isi[D[A]]++;
	isi[D[B]]++;
	isi[D[A]-1]--;
	isi[D[B]-1]--;
	tot+=2;
	has=0;
	te=0;
	for(i=0;i<n;i++)
		if(b[i]!=Z)
			dfs(i,i);
	for(i=0;i<n;i++)
	{
		ll CCC=CC,ada=1;
		isi[D[i]]--;
		for(j=0;j<v[i].size();j++)
		{
			if(br[w[i][j]]==Z)
			{
			//	cout<<i<<" "<<v[i][j]<<"_\n";
				CCC++;
			}
			else
				ada=0;
			isi[D[v[i][j]]]--;
			isi[D[v[i][j]]-1]++;
		}
		if(ada||D[i]==0)
			CCC--;
		//cout<<n*2-CC
	//	cout<<CCC<<" "<<(n-1)*2-CCC*2<<" "<<tot-D[i]*2<<" "<<(isi[0]+isi[1]+isi[2])<<"\n";
		has+=(((isi[0]+isi[1]+isi[2])==n-1)&&(((n-1)*2-CCC*2)==(tot-D[i]*2)));
//		if((isi[0]+isi[1]+isi[2])==n-1)
//			cout<<i<<"_\n";
		isi[D[i]]++;
		for(j=0;j<v[i].size();j++)
		{
			isi[D[v[i][j]]]++;
			isi[D[v[i][j]]-1]--;
		}
	}
}
int CountCritical() 
{	
	return has;
}

Compilation message

rings.cpp: In function 'void dfs(ll, ll)':
rings.cpp:38:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ii=0;ii<v[aa].size();ii++)
           ~~^~~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:80:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<v[i].size();j++)
           ~^~~~~~~~~~~~
rings.cpp:100:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<v[i].size();j++)
           ~^~~~~~~~~~~~

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	63608 KB	Output is correct
2	Correct	839 ms	64248 KB	Output is correct
3	Correct	1226 ms	64256 KB	Output is correct
4	Correct	81 ms	63864 KB	Output is correct
5	Correct	408 ms	64048 KB	Output is correct
6	Correct	1216 ms	64376 KB	Output is correct
7	Correct	98 ms	63864 KB	Output is correct
8	Correct	707 ms	64064 KB	Output is correct
9	Correct	1234 ms	64248 KB	Output is correct
10	Correct	1249 ms	64288 KB	Output is correct

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	4097 ms	78588 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	63608 KB	Output is correct
2	Correct	839 ms	64248 KB	Output is correct
3	Correct	1226 ms	64256 KB	Output is correct
4	Correct	81 ms	63864 KB	Output is correct
5	Correct	408 ms	64048 KB	Output is correct
6	Correct	1216 ms	64376 KB	Output is correct
7	Correct	98 ms	63864 KB	Output is correct
8	Correct	707 ms	64064 KB	Output is correct
9	Correct	1234 ms	64248 KB	Output is correct
10	Correct	1249 ms	64288 KB	Output is correct
11	Correct	1263 ms	64388 KB	Output is correct
12	Execution timed out	4097 ms	64696 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	63608 KB	Output is correct
2	Correct	839 ms	64248 KB	Output is correct
3	Correct	1226 ms	64256 KB	Output is correct
4	Correct	81 ms	63864 KB	Output is correct
5	Correct	408 ms	64048 KB	Output is correct
6	Correct	1216 ms	64376 KB	Output is correct
7	Correct	98 ms	63864 KB	Output is correct
8	Correct	707 ms	64064 KB	Output is correct
9	Correct	1234 ms	64248 KB	Output is correct
10	Correct	1249 ms	64288 KB	Output is correct
11	Correct	1263 ms	64388 KB	Output is correct
12	Execution timed out	4097 ms	64696 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	63608 KB	Output is correct
2	Correct	839 ms	64248 KB	Output is correct
3	Correct	1226 ms	64256 KB	Output is correct
4	Correct	81 ms	63864 KB	Output is correct
5	Correct	408 ms	64048 KB	Output is correct
6	Correct	1216 ms	64376 KB	Output is correct
7	Correct	98 ms	63864 KB	Output is correct
8	Correct	707 ms	64064 KB	Output is correct
9	Correct	1234 ms	64248 KB	Output is correct
10	Correct	1249 ms	64288 KB	Output is correct
11	Execution timed out	4097 ms	78588 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-