oj.uz

Submission #342921

# Submission time Handle Problem Language Result Execution time Memory
342921 2021-01-03T08:24:42 Z inwbear Split the Attractions (IOI19_split) C++14
18 / 100
 167 ms 23020 KB 
#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
vector<int>v[100005],cn[100005];
vector<pii>gr;
bitset<100005>vis;
int ch[100005],mn,pos,rr,re[100005];

void dfs(int N)
{
	if(re[N]!=0)return;
	vis[N]=true;
	ch[N]=1;
	for(int i=0;i<v[N].size();i++)
	{
		if((!vis[v[N][i]])&&re[v[N][i]]==0)
		{
			dfs(v[N][i]);
			ch[N]+=ch[v[N][i]];
			cn[N].pb(v[N][i]);
		}
	}
	//printf("[%d %d]\n",N,ch[N]);
	return;
}

void grdiv(int N,int ty)
{
	if(rr>=gr[ty].F||re[N]!=0)return;
	ch[N]=0;
	rr++,re[N]=gr[ty].S;
	for(int i=0;i<cn[N].size();i++)
	{
		grdiv(cn[N][i],ty);
	}
	return;
}

vector<int>find_split(int n,int a,int b,int c,vector<int>p,vector<int>q)
{
	vector<int>ans(n);
	gr.pb({a,1});
	gr.pb({b,2});
	gr.pb({c,3});
	sort(all(gr));
	for(int i=0;i<p.size();i++)
	{
		v[p[i]].pb(q[i]);
		v[q[i]].pb(p[i]);
	}
	dfs(0);
	mn=imx,rr=1;
	for(int i=0;i<n;i++)
	{
		if(ch[i]>=gr[0].F&&ch[i]<mn)
		{
			mn=ch[i];
			pos=i;
		}
	}
	re[pos]=gr[0].S,ch[pos]=0;
	for(int i=0;i<cn[pos].size();i++)grdiv(cn[pos][i],0);
	for(int i=0;i<n;i++)vis[i]=false;
	dfs(0);
	mn=imx,rr=1;
	for(int i=0;i<n;i++)
	{
		if(ch[i]>=gr[1].F&&ch[i]<mn)
		{
			mn=ch[i];
			pos=i;
		}
	}
	if(mn!=imx)
	{
		re[pos]=gr[1].S,ch[pos]=0;
		for(int i=0;i<cn[pos].size();i++)grdiv(cn[pos][i],1);
		for(int i=0;i<n;i++)
		{
			//printf("%d ",re[i]);
			if(re[i]==0)ans[i]=gr[2].S;
			else ans[i]=re[i];
		}
		//printf("\n");
	}
	return ans;
}

Compilation message

split.cpp: In function 'void dfs(int)':
split.cpp:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i=0;i<v[N].size();i++)
      |              ~^~~~~~~~~~~~
split.cpp: In function 'void grdiv(int, int)':
split.cpp:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i=0;i<cn[N].size();i++)
      |              ~^~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:56:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i=0;i<p.size();i++)
      |              ~^~~~~~~~~
split.cpp:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i=0;i<cn[pos].size();i++)grdiv(cn[pos][i],0);
      |              ~^~~~~~~~~~~~~~~
split.cpp:87:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int i=0;i<cn[pos].size();i++)grdiv(cn[pos][i],1);
      |               ~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB ok, correct split
2 Correct 3 ms 4972 KB ok, correct split
3 Correct 3 ms 4972 KB ok, correct split
4 Correct 3 ms 4972 KB ok, correct split
5 Correct 3 ms 4972 KB ok, correct split
6 Correct 4 ms 4972 KB ok, correct split
7 Correct 143 ms 22636 KB ok, correct split
8 Correct 139 ms 19948 KB ok, correct split
9 Correct 148 ms 19692 KB ok, correct split
10 Correct 146 ms 22636 KB ok, correct split
11 Correct 140 ms 23020 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB ok, correct split
2 Correct 4 ms 4972 KB ok, correct split
3 Correct 3 ms 4972 KB ok, correct split
4 Correct 155 ms 17516 KB ok, correct split
5 Correct 114 ms 13164 KB ok, correct split
6 Correct 155 ms 21484 KB ok, correct split
7 Correct 151 ms 19052 KB ok, correct split
8 Correct 167 ms 15468 KB ok, correct split
9 Correct 137 ms 14188 KB ok, correct split
10 Correct 60 ms 12260 KB ok, correct split
11 Correct 59 ms 12388 KB ok, correct split
12 Correct 62 ms 12260 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB ok, correct split
2 Incorrect 91 ms 12764 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB ok, correct split
2 Correct 4 ms 4972 KB ok, no valid answer
3 Correct 4 ms 4972 KB ok, correct split
4 Correct 4 ms 4972 KB ok, correct split
5 Correct 4 ms 4972 KB ok, correct split
6 Correct 4 ms 4972 KB ok, correct split
7 Correct 4 ms 4972 KB ok, correct split
8 Correct 3 ms 4972 KB ok, correct split
9 Correct 6 ms 5356 KB ok, correct split
10 Correct 6 ms 5356 KB ok, correct split
11 Correct 4 ms 5100 KB ok, correct split
12 Correct 6 ms 5356 KB ok, correct split
13 Correct 5 ms 4972 KB ok, correct split
14 Correct 4 ms 4972 KB ok, correct split
15 Correct 3 ms 4972 KB ok, correct split
16 Correct 3 ms 4972 KB ok, correct split
17 Correct 3 ms 4972 KB ok, correct split
18 Correct 3 ms 4972 KB ok, correct split
19 Correct 4 ms 5100 KB ok, correct split
20 Correct 5 ms 5100 KB ok, correct split
21 Correct 5 ms 5356 KB ok, correct split
22 Incorrect 5 ms 5356 KB jury found a solution, contestant did not
23 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB ok, correct split
2 Correct 3 ms 4972 KB ok, correct split
3 Correct 3 ms 4972 KB ok, correct split
4 Correct 3 ms 4972 KB ok, correct split
5 Correct 3 ms 4972 KB ok, correct split
6 Correct 4 ms 4972 KB ok, correct split
7 Correct 143 ms 22636 KB ok, correct split
8 Correct 139 ms 19948 KB ok, correct split
9 Correct 148 ms 19692 KB ok, correct split
10 Correct 146 ms 22636 KB ok, correct split
11 Correct 140 ms 23020 KB ok, correct split
12 Correct 4 ms 4992 KB ok, correct split
13 Correct 4 ms 4972 KB ok, correct split
14 Correct 3 ms 4972 KB ok, correct split
15 Correct 155 ms 17516 KB ok, correct split
16 Correct 114 ms 13164 KB ok, correct split
17 Correct 155 ms 21484 KB ok, correct split
18 Correct 151 ms 19052 KB ok, correct split
19 Correct 167 ms 15468 KB ok, correct split
20 Correct 137 ms 14188 KB ok, correct split
21 Correct 60 ms 12260 KB ok, correct split
22 Correct 59 ms 12388 KB ok, correct split
23 Correct 62 ms 12260 KB ok, correct split
24 Correct 3 ms 4972 KB ok, correct split
25 Incorrect 91 ms 12764 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -