Submission #116589

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116589	2019-06-13T03:20:07 Z	faustaadp	Parachute rings (IOI12_rings)	C++17	20 / 100	4000 ms	175808 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,toe;
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]=toe;
	ll ii;
	for(ii=0;ii<v[aa].size();ii++)
	{
		if(v[aa][ii]==bb)continue;
		if(b[v[aa][ii]]!=toe)
		{
			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]]=toe;
	}
}
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;
}
int CountCritical() 
{	
	has=0;
	te=0;
	toe++;
	for(i=0;i<n;i++)
		if(b[i]!=toe)
			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]]==toe)
			{
			//	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--;
		has+=(((isi[0]+isi[1]+isi[2])==n-1)&&(((n-1)*2-CCC*2)==(tot-D[i]*2)));
		isi[D[i]]++;
		for(j=0;j<v[i].size();j++)
		{
			isi[D[v[i][j]]]++;
			isi[D[v[i][j]]-1]--;
		}
	}
	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 'int CountCritical()':
rings.cpp:84: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	55 ms	63608 KB	Output is correct
2	Correct	58 ms	63992 KB	Output is correct
3	Correct	58 ms	64120 KB	Output is correct
4	Correct	56 ms	63736 KB	Output is correct
5	Correct	56 ms	63992 KB	Output is correct
6	Correct	64 ms	64376 KB	Output is correct
7	Correct	56 ms	63864 KB	Output is correct
8	Correct	62 ms	63992 KB	Output is correct
9	Correct	75 ms	64248 KB	Output is correct
10	Correct	60 ms	64120 KB	Output is correct

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1696 ms	112604 KB	Output is correct
2	Correct	3321 ms	139120 KB	Output is correct
3	Correct	3564 ms	175808 KB	Output is correct
4	Execution timed out	4109 ms	158064 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	63608 KB	Output is correct
2	Correct	58 ms	63992 KB	Output is correct
3	Correct	58 ms	64120 KB	Output is correct
4	Correct	56 ms	63736 KB	Output is correct
5	Correct	56 ms	63992 KB	Output is correct
6	Correct	64 ms	64376 KB	Output is correct
7	Correct	56 ms	63864 KB	Output is correct
8	Correct	62 ms	63992 KB	Output is correct
9	Correct	75 ms	64248 KB	Output is correct
10	Correct	60 ms	64120 KB	Output is correct
11	Correct	74 ms	64248 KB	Output is correct
12	Correct	124 ms	65048 KB	Output is correct
13	Correct	115 ms	65016 KB	Output is correct
14	Incorrect	95 ms	64408 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	63608 KB	Output is correct
2	Correct	58 ms	63992 KB	Output is correct
3	Correct	58 ms	64120 KB	Output is correct
4	Correct	56 ms	63736 KB	Output is correct
5	Correct	56 ms	63992 KB	Output is correct
6	Correct	64 ms	64376 KB	Output is correct
7	Correct	56 ms	63864 KB	Output is correct
8	Correct	62 ms	63992 KB	Output is correct
9	Correct	75 ms	64248 KB	Output is correct
10	Correct	60 ms	64120 KB	Output is correct
11	Correct	74 ms	64248 KB	Output is correct
12	Correct	124 ms	65048 KB	Output is correct
13	Correct	115 ms	65016 KB	Output is correct
14	Incorrect	95 ms	64408 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	63608 KB	Output is correct
2	Correct	58 ms	63992 KB	Output is correct
3	Correct	58 ms	64120 KB	Output is correct
4	Correct	56 ms	63736 KB	Output is correct
5	Correct	56 ms	63992 KB	Output is correct
6	Correct	64 ms	64376 KB	Output is correct
7	Correct	56 ms	63864 KB	Output is correct
8	Correct	62 ms	63992 KB	Output is correct
9	Correct	75 ms	64248 KB	Output is correct
10	Correct	60 ms	64120 KB	Output is correct
11	Correct	1696 ms	112604 KB	Output is correct
12	Correct	3321 ms	139120 KB	Output is correct
13	Correct	3564 ms	175808 KB	Output is correct
14	Execution timed out	4109 ms	158064 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-