#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 n,m,i,j,t,a[5],rs[nmax],x,b,sz[nmax];
vector<int>vc,g[nmax],c;
void rec(int x,int p)
{
for(int i=0;i<c.size();i++)
{
if(!a[c[i]])continue;
a[c[i]]--;
rs[x]=c[i];
break;
}
for(int i=0;i<g[x].size();i++)
{
int y=g[x][i];
if(y==p)continue;
rec(y,x);
}
}
void dfs(int x,int p)
{
sz[x]=1;
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];
}
if(!b)
{
for(int i=1;i<=3;i++)
{
for(int j=i+1;j<=3;j++)
{
if(a[i]+a[j]!=sz[x])continue;
c.pb(i);
c.pb(j);
rec(x,p);
b=1;
break;
}
if(b)break;
}
if(!b)
{
for(int i=1;i<=3;i++)
{
if(a[i]!=sz[x])continue;
c.pb(i);
rec(x,p);
b=1;
break;
}
}
}
}
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=P.size();
for(i=0;i<m;i++)
{
P[i]++,Q[i]++;
g[P[i]].pb(Q[i]);
g[Q[i]].pb(P[i]);
}
dfs(1,0);
if(b)
{
for(i=1;i<=n;i++)
{
if(rs[i])continue;
for(j=1;j<=3;j++)
{
if(!a[j])continue;
rs[i]=j;
a[j]--;
break;
}
}
}
for(i=1;i<=n;i++)vc.pb(rs[i]);
return vc;
}
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 rec(int, int)':
split.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<c.size();i++)
~^~~~~~~~~
split.cpp:33: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 dfs(int, int)':
split.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[x].size();i++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
ok, correct split |
| 2 |
Runtime error |
912 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
ok, correct split |
| 2 |
Runtime error |
882 ms |
1048576 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
ok, correct split |
| 2 |
Incorrect |
85 ms |
9960 KB |
jury found a solution, contestant did not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
884 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
ok, correct split |
| 2 |
Runtime error |
912 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
