oj.uz

Submission #158223

# Submission time Handle Problem Language Result Execution time Memory
158223 2019-10-15T14:46:34 Z MvC Split the Attractions (IOI19_split) C++14
22 / 100
 1036 ms 1048580 KB 
#include "split.h"
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int sz[nmax],pr[nmax],a[5],n,nd,c1,c2,i,m;
vector<int>g[nmax],rs;
bitset<nmax>viz;
void dfs(int x,int p)
{
	sz[x]=1;
	pr[x]=p;
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i];
		if(y==p)continue;
		dfs(y,x);
		sz[x]+=sz[y];
	}
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			if(i==j)continue;
			if(a[i]<=sz[x] && sz[x]<=a[i]+a[j])
			{
				nd=x;
				c1=i;
				c2=6-i-j;
			}
		}
	}
}
void col(int x,int c)
{
	if(!a[c])return;
	rs[x-1]=c;
	a[c]--;
	viz[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i];
		if(y==pr[x] || viz[y])continue;
		col(y,c);
	}
}
vector<int> find_split(int N,int A,int B,int C,vector<int>P,vector<int>Q) 
{
	n=N,a[1]=A,a[2]=B,a[3]=C,m=(int)P.size();
	for(i=0;i<m;i++)
	{
		P[i]++,Q[i]++;
		g[P[i]].pb(Q[i]);
		g[Q[i]].pb(P[i]);
	}
	nd=-1;
	dfs(1,0);
	for(i=1;i<=n;i++)rs.pb(0);
	if(nd!=-1)
	{
		col(nd,c1);
		col(1,c2);
		for(i=0;i<n;i++)if(!rs[i])rs[i]=6-c1-c2;
	}
	return rs;
}

Compilation message

split.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
split.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
split.cpp: In function 'void dfs(int, int)':
split.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~
split.cpp: In function 'void col(int, int)':
split.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[x].size();i++)
              ~^~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Runtime error 1036 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Runtime error 937 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 88 ms 9168 KB ok, correct split
3 Correct 34 ms 5880 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 101 ms 12336 KB ok, correct split
6 Correct 98 ms 12148 KB ok, correct split
7 Correct 91 ms 12020 KB ok, correct split
8 Correct 111 ms 13044 KB ok, correct split
9 Correct 96 ms 11892 KB ok, correct split
10 Correct 30 ms 5240 KB ok, no valid answer
11 Correct 40 ms 6644 KB ok, no valid answer
12 Correct 74 ms 10608 KB ok, no valid answer
13 Correct 80 ms 10352 KB ok, no valid answer
14 Correct 71 ms 10608 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 972 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Runtime error 1036 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -