Submission #116587

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116587	2019-06-13T03:15:55 Z	faustaadp	Parachute rings (IOI12_rings)	C++17	20 / 100	4000 ms	175952 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;
}
int CountCritical() 
{	
	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--;
		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:83:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<v[i].size();j++)
           ~^~~~~~~~~~~~
rings.cpp:99: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	57 ms	64120 KB	Output is correct
3	Correct	59 ms	64120 KB	Output is correct
4	Correct	55 ms	63748 KB	Output is correct
5	Correct	57 ms	63992 KB	Output is correct
6	Correct	60 ms	64376 KB	Output is correct
7	Correct	56 ms	63864 KB	Output is correct
8	Correct	57 ms	64076 KB	Output is correct
9	Correct	58 ms	64220 KB	Output is correct
10	Correct	59 ms	64200 KB	Output is correct

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1652 ms	112576 KB	Output is correct
2	Correct	3217 ms	139140 KB	Output is correct
3	Correct	3625 ms	175952 KB	Output is correct
4	Execution timed out	4093 ms	158068 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	57 ms	64120 KB	Output is correct
3	Correct	59 ms	64120 KB	Output is correct
4	Correct	55 ms	63748 KB	Output is correct
5	Correct	57 ms	63992 KB	Output is correct
6	Correct	60 ms	64376 KB	Output is correct
7	Correct	56 ms	63864 KB	Output is correct
8	Correct	57 ms	64076 KB	Output is correct
9	Correct	58 ms	64220 KB	Output is correct
10	Correct	59 ms	64200 KB	Output is correct
11	Correct	70 ms	64192 KB	Output is correct
12	Correct	118 ms	65016 KB	Output is correct
13	Correct	124 ms	65232 KB	Output is correct
14	Incorrect	92 ms	64376 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	57 ms	64120 KB	Output is correct
3	Correct	59 ms	64120 KB	Output is correct
4	Correct	55 ms	63748 KB	Output is correct
5	Correct	57 ms	63992 KB	Output is correct
6	Correct	60 ms	64376 KB	Output is correct
7	Correct	56 ms	63864 KB	Output is correct
8	Correct	57 ms	64076 KB	Output is correct
9	Correct	58 ms	64220 KB	Output is correct
10	Correct	59 ms	64200 KB	Output is correct
11	Correct	70 ms	64192 KB	Output is correct
12	Correct	118 ms	65016 KB	Output is correct
13	Correct	124 ms	65232 KB	Output is correct
14	Incorrect	92 ms	64376 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	57 ms	64120 KB	Output is correct
3	Correct	59 ms	64120 KB	Output is correct
4	Correct	55 ms	63748 KB	Output is correct
5	Correct	57 ms	63992 KB	Output is correct
6	Correct	60 ms	64376 KB	Output is correct
7	Correct	56 ms	63864 KB	Output is correct
8	Correct	57 ms	64076 KB	Output is correct
9	Correct	58 ms	64220 KB	Output is correct
10	Correct	59 ms	64200 KB	Output is correct
11	Correct	1652 ms	112576 KB	Output is correct
12	Correct	3217 ms	139140 KB	Output is correct
13	Correct	3625 ms	175952 KB	Output is correct
14	Execution timed out	4093 ms	158068 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-