oj.uz

Submission #121166

# Submission time Handle Problem Language Result Execution time Memory
121166 2019-06-26T07:26:11 Z baluteshih Parachute rings (IOI12_rings) C++14
0 / 100
 3604 ms 99100 KB 
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int C=5;
int N,boss[5][1000005],upd,tag[1000005],flag,flag2,ans[C],sz[C][1000005],cir;
vector<int> G[1000005],pos;

void Init(int N_)
{
	N=N_;
	for(int j=0;j<4;++j)
		ans[j]=1;
	for(int i=0;i<N;++i)
		for(int j=0;j<C;++j)
			boss[j][i]=i;
}

int finds(int t,int a)
{
	if(boss[t][a]==a) return a;
	return boss[t][a]=finds(t,boss[t][a]);
}

bool Union(int t,int a,int b)
{
	a=finds(t,a),b=finds(t,b);
	if(a==b) return 0;
	return boss[t][a]=b;
}

void update(int x)
{
	++upd,pos.pb(x);
	for(int i:G[x])
		pos.pb(i);
	for(int i=0;i<pos.size();++i)
		for(int j=0;j<N;++j)
			if(j!=pos[i])	
			{
				for(int k:G[j])
					if(k!=pos[i]&&j<k)
						ans[i]&=Union(i,j,k),++sz[i][j],++sz[i][k];
				ans[i]&=(sz[i][j]<3);
			}
}

void add_edge(int a,int b)
{
	for(int i=0;i<4;++i)
		if(a!=pos[i]&&b!=pos[i])
		{
			ans[i]&=Union(i,a,b);
			++sz[i][a],++sz[i][b];
			ans[i]&=(sz[i][a]<3),ans[i]&=(sz[i][b]<3);
		}
}

void Link(int A, int B)
{
	G[A].pb(B),G[B].pb(A);
	if(flag) add_edge(A,B);
	if(!flag&&G[A].size()==3) flag=1,update(A);
	if(!flag&&G[B].size()==3) flag=1,update(B);
	if(!flag)
		if(!Union(4,A,B))
			if(!flag2)
				for(int i=(flag2=1,0);i<N;++i)
					cir+=(finds(4,i)==finds(4,A));
			else
				cir=0;
}

int CountCritical()
{
	if(flag) return ans[0]+ans[1]+ans[2]+ans[3];
	if(flag2) return cir;
	return N;
}

Compilation message

rings.cpp: In function 'bool Union(int, int, int)':
rings.cpp:40:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  return boss[t][a]=b;
         ~~~~~~~~~~^~
rings.cpp: In function 'void update(int)':
rings.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pos.size();++i)
              ~^~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:77:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   if(!Union(4,A,B))
     ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 23936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 57372 KB Output is correct
2 Correct 2353 ms 87840 KB Output is correct
3 Correct 3604 ms 99100 KB Output is correct
4 Correct 1320 ms 88184 KB Output is correct
5 Incorrect 1316 ms 88244 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 23936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 23936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 23936 KB Output isn't correct
2 Halted 0 ms 0 KB -