oj.uz

답안 #116585

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116585 2019-06-13T03:14:00 Z faustaadp 낙하산 고리들 (IOI12_rings) C++17
20 / 100
 4000 ms 78588 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4097 ms 78588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -