oj.uz

Submission #152873

# Submission time Handle Problem Language Result Execution time Memory
152873 2019-09-10T09:38:15 Z tinjyu Split the Attractions (IOI19_split) C++14
18 / 100
 2000 ms 19704 KB 
#include "split.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h> 
using namespace std;
long long int map2[1000005][2],road2[100005],cnt=0,x1[100005],y1[100005],can=0,ans[100005],f[100005],s,e,stop,a[2],b[2],c[2],sum[100005],t[100005],n,m,road[100005],map[1000005][2],tag[100005];
int buildp(int x,int father)
{
	tag[x]=1;
	f[x]=father;
	sum[x]=1;
	int g=road[x];
	while(g!=-1)
	{
		int now=map[g][0];
		if(tag[now]==0)sum[x]+=buildp(now,x);
		g=map[g][1];
	}
	return sum[x];
}
int color(int x,int col)
{
	if(s==e)return 0;
	s++;
	ans[x]=col;
	int g=road[x];
	while(g!=-1)
	{
		if(s==e)return 0;
		int now=map[g][0];
		if(now!=f[x] && now!=stop)color(now,col);
		g=map[g][1];
	}
}
int find(int x,int father)
{
	if(sum[x]>=a[0] && father>=b[0])
	{	
		can=1;
		stop=f[x];
		s=0;
		e=a[0];
		color(x,a[1]);
		stop=x;
		s=0;
		e=b[0];
		color(0,b[1]);
		return 0;
	}
	if(father>=a[0] && sum[x]>=b[0])
	{
		can=1;
		stop=x;
		s=0;
		e=a[0];
		color(0,a[1]);
		stop=f[x];
		s=0;
		e=b[0];
		color(x,b[1]);
		return 0;
	}
	int g=road[x];
	while(g!=-1)
	{
		int now=map[g][0];
		if(now!=f[x])find(now,father+(sum[x]-sum[now]));
		if(can==1)return 0;
		g=map[g][1];
	}
}
int dfs(int x)
{
	int g=road2[x];
	tag[x]=1;
	while(g!=-1)
	{
		int now=map2[g][0];
		if(tag[now]==0)
		{
			y1[cnt]=x;
			x1[cnt]=now;
			cnt++;
			dfs(now);
		}
		g=map2[g][1];
	}
	return 0;
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
	a[0]=A;
	a[1]=1;
	b[0]=B;
	b[1]=2;
	c[0]=C;
	c[1]=3;

	if(b[0]<=a[0] && b[0]<=c[0])
	{
		swap(a[0],b[0]);
		swap(a[1],b[1]);
	}
	if(c[0]<=b[0] && c[0]<=a[0])
	{
		swap(a[0],c[0]);
		swap(a[1],c[1]);
	}
	if(c[0]<=b[0])
	{
		swap(b[0],c[0]);
		swap(b[1],c[1]);
	}
	n=N;
	m=q.size();
	for(int i=0;i<=n;i++)road2[i]=-1;
	for(int i=0;i<m;i++)
	{
		map2[i*2][0]=p[i];
		map2[i*2][1]=road2[q[i]];
		road2[q[i]]=i*2;
		map2[i*2+1][0]=q[i];
		map2[i*2+1][1]=road2[p[i]];
		road2[p[i]]=i*2+1;
	}
	int qw=0;
	while(qw<n)
	{
		cnt=0;
		dfs(qw);
		for(int i=0;i<=n;i++)
		{
			road[i]=-1;
			tag[i]=0;
		}
		
		for(int i=0;i<cnt;i++)
		{
			map[i*2][0]=x1[i];
			map[i*2][1]=road[y1[i]];
			road[y1[i]]=i*2;
			map[i*2+1][0]=y1[i];
			map[i*2+1][1]=road[x1[i]];
			road[x1[i]]=i*2+1;
		}
		can=0;
		buildp(0,-1);
		find(0,0);
		if(can==1)
		{
			vector<int> res(n);
			for(int i=0;i<n;i++)
			{
				res[i]=ans[i];
				if(res[i]==0)res[i]=c[1];
			} 
			return res;
		}
		qw++;
	}
	vector<int> res(n);
}

Compilation message

split.cpp: In function 'int color(int, int)':
split.cpp:35:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
split.cpp: In function 'int find(int, int)':
split.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:162:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 348 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Correct 2 ms 380 KB ok, correct split
7 Correct 83 ms 18556 KB ok, correct split
8 Correct 74 ms 16760 KB ok, correct split
9 Correct 74 ms 17144 KB ok, correct split
10 Correct 78 ms 17812 KB ok, correct split
11 Correct 87 ms 18580 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 88 ms 18444 KB ok, correct split
5 Correct 67 ms 15352 KB ok, correct split
6 Correct 82 ms 17708 KB ok, correct split
7 Correct 75 ms 17404 KB ok, correct split
8 Correct 103 ms 19704 KB ok, correct split
9 Correct 69 ms 15480 KB ok, correct split
10 Correct 55 ms 15352 KB ok, correct split
11 Correct 55 ms 15352 KB ok, correct split
12 Correct 58 ms 15608 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 70 ms 15472 KB ok, correct split
3 Correct 27 ms 6524 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 73 ms 16504 KB ok, correct split
6 Correct 68 ms 16376 KB ok, correct split
7 Correct 70 ms 16376 KB ok, correct split
8 Correct 86 ms 16888 KB ok, correct split
9 Correct 83 ms 16376 KB ok, correct split
10 Execution timed out 2047 ms 5124 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Incorrect 2 ms 376 KB WA in grader: Invalid length of the result.
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 348 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Correct 2 ms 380 KB ok, correct split
7 Correct 83 ms 18556 KB ok, correct split
8 Correct 74 ms 16760 KB ok, correct split
9 Correct 74 ms 17144 KB ok, correct split
10 Correct 78 ms 17812 KB ok, correct split
11 Correct 87 ms 18580 KB ok, correct split
12 Correct 2 ms 376 KB ok, correct split
13 Correct 2 ms 376 KB ok, correct split
14 Correct 2 ms 376 KB ok, correct split
15 Correct 88 ms 18444 KB ok, correct split
16 Correct 67 ms 15352 KB ok, correct split
17 Correct 82 ms 17708 KB ok, correct split
18 Correct 75 ms 17404 KB ok, correct split
19 Correct 103 ms 19704 KB ok, correct split
20 Correct 69 ms 15480 KB ok, correct split
21 Correct 55 ms 15352 KB ok, correct split
22 Correct 55 ms 15352 KB ok, correct split
23 Correct 58 ms 15608 KB ok, correct split
24 Correct 2 ms 376 KB ok, correct split
25 Correct 70 ms 15472 KB ok, correct split
26 Correct 27 ms 6524 KB ok, correct split
27 Correct 2 ms 376 KB ok, correct split
28 Correct 73 ms 16504 KB ok, correct split
29 Correct 68 ms 16376 KB ok, correct split
30 Correct 70 ms 16376 KB ok, correct split
31 Correct 86 ms 16888 KB ok, correct split
32 Correct 83 ms 16376 KB ok, correct split
33 Execution timed out 2047 ms 5124 KB Time limit exceeded
34 Halted 0 ms 0 KB -