oj.uz

Submission #773076

# Submission time Handle Problem Language Result Execution time Memory
773076 2023-07-04T14:46:47 Z Trumling Split the Attractions (IOI19_split) C++14
22 / 100
 695 ms 1048576 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()

int n,a,b,c;
vector<int>p,q;
vector<vector<int>>g;
vector<int> res;
vector<int>child;

void cfind(int start,int pre)
{
	for(auto x:g[start])
	if(x!=pre)
	{
		cfind(x,start);
		child[start]+=child[x]+1;
	}

}

vector<int> find_split(int nn, int aa, int bb, int cc, vector<int> pp, vector<int> qq) {

p=pp;
q=qq;
n=nn;
a=aa;
b=bb;
c=cc;

g.assign(n,vector<int>());
res.assign(n,0);
child.assign(n,0);

ll m=p.size();

for(int i=0;i<m;i++)
{
	g[p[i]].pb(q[i]);
	g[q[i]].pb(p[i]);

}
cfind(0,0);
vector<pair<int,int>>arr(3);

arr[0]={a,1};
arr[1]={b,2};
arr[2]={c,3};

do
{
bool tf=0;

for(int i=1;i<n;i++)
{
if(child[i]+1<arr[0].F || child[0]-child[i]<arr[1].F)
continue;

queue<int>q;
q.push(i);
ll count=1;
vector<bool>vis(n,0);

while(!q.empty())
{
ll curr=q.front();
q.pop();
vis[curr]=1;
res[curr]=arr[0].S;
 
for(auto x:g[curr])
if(!vis[x] && count<arr[0].F && child[x]<child[curr])
{
	vis[x]=1;
	q.push(x);
	count++;
}
}

q.push(0);
count=1;

while(!q.empty())
{
ll curr=q.front();
q.pop();
vis[curr]=1;
res[curr]=arr[1].S;
 
for(auto x:g[curr])
if(!vis[x] && count<arr[1].F)
{
	vis[x]=1;
	q.push(x);
	count++;
}
}

for(int i=0;i<n;i++)
if(!res[i])
res[i]=arr[2].S;

tf=1;
break;

}
if(tf)
break;	
} while (next_permutation(all(arr)));

return  res;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok, correct split
2 Runtime error 684 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB ok, correct split
2 Runtime error 695 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB ok, correct split
2 Correct 39 ms 9520 KB ok, correct split
3 Correct 15 ms 4324 KB ok, correct split
4 Correct 0 ms 212 KB ok, correct split
5 Correct 51 ms 12500 KB ok, correct split
6 Correct 40 ms 12236 KB ok, correct split
7 Correct 41 ms 12080 KB ok, correct split
8 Correct 56 ms 13296 KB ok, correct split
9 Correct 41 ms 11980 KB ok, correct split
10 Correct 12 ms 3628 KB ok, no valid answer
11 Correct 19 ms 5424 KB ok, no valid answer
12 Correct 34 ms 10664 KB ok, no valid answer
13 Correct 39 ms 10472 KB ok, no valid answer
14 Correct 33 ms 10740 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 407 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB ok, correct split
2 Runtime error 684 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -