Submission #116584

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116584	2019-06-13T03:12:59 Z	faustaadp	Parachute rings (IOI12_rings)	C++17	20 / 100	4000 ms	188536 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;
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 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;
}
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;
	}
}
int CountCritical() 
{	
	ll 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]--;
		}
	}
	return has;
}

Compilation message

rings.cpp: In function 'void dfs(ll, ll)':
rings.cpp:58: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:103: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	54 ms	63480 KB	Output is correct
2	Correct	60 ms	64120 KB	Output is correct
3	Correct	57 ms	64224 KB	Output is correct
4	Correct	55 ms	63824 KB	Output is correct
5	Correct	58 ms	63992 KB	Output is correct
6	Correct	63 ms	64376 KB	Output is correct
7	Correct	56 ms	63864 KB	Output is correct
8	Correct	61 ms	64124 KB	Output is correct
9	Correct	61 ms	64248 KB	Output is correct
10	Correct	60 ms	64376 KB	Output is correct

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1683 ms	119436 KB	Output is correct
2	Correct	3147 ms	149880 KB	Output is correct
3	Correct	3668 ms	188536 KB	Output is correct
4	Execution timed out	4108 ms	171600 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	63480 KB	Output is correct
2	Correct	60 ms	64120 KB	Output is correct
3	Correct	57 ms	64224 KB	Output is correct
4	Correct	55 ms	63824 KB	Output is correct
5	Correct	58 ms	63992 KB	Output is correct
6	Correct	63 ms	64376 KB	Output is correct
7	Correct	56 ms	63864 KB	Output is correct
8	Correct	61 ms	64124 KB	Output is correct
9	Correct	61 ms	64248 KB	Output is correct
10	Correct	60 ms	64376 KB	Output is correct
11	Correct	72 ms	64324 KB	Output is correct
12	Correct	126 ms	65092 KB	Output is correct
13	Correct	132 ms	65144 KB	Output is correct
14	Incorrect	89 ms	64504 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	63480 KB	Output is correct
2	Correct	60 ms	64120 KB	Output is correct
3	Correct	57 ms	64224 KB	Output is correct
4	Correct	55 ms	63824 KB	Output is correct
5	Correct	58 ms	63992 KB	Output is correct
6	Correct	63 ms	64376 KB	Output is correct
7	Correct	56 ms	63864 KB	Output is correct
8	Correct	61 ms	64124 KB	Output is correct
9	Correct	61 ms	64248 KB	Output is correct
10	Correct	60 ms	64376 KB	Output is correct
11	Correct	72 ms	64324 KB	Output is correct
12	Correct	126 ms	65092 KB	Output is correct
13	Correct	132 ms	65144 KB	Output is correct
14	Incorrect	89 ms	64504 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	63480 KB	Output is correct
2	Correct	60 ms	64120 KB	Output is correct
3	Correct	57 ms	64224 KB	Output is correct
4	Correct	55 ms	63824 KB	Output is correct
5	Correct	58 ms	63992 KB	Output is correct
6	Correct	63 ms	64376 KB	Output is correct
7	Correct	56 ms	63864 KB	Output is correct
8	Correct	61 ms	64124 KB	Output is correct
9	Correct	61 ms	64248 KB	Output is correct
10	Correct	60 ms	64376 KB	Output is correct
11	Correct	1683 ms	119436 KB	Output is correct
12	Correct	3147 ms	149880 KB	Output is correct
13	Correct	3668 ms	188536 KB	Output is correct
14	Execution timed out	4108 ms	171600 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-