Submission #745498

#	Time	Username	Problem	Language	Result	Execution time	Memory
745498		MohamedAliSaidane	Split the Attractions (IOI19_split)	C++14	22 / 100	483 ms	1048576 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;


typedef long long ll;

typedef vector<int> vi;

#define pb push_back
#define ff first
#define ss second

const int nax = 1e5 + 4;
int n, m, a, b, c;
vi adj[nax];
vi ans;
int d[nax], sz[nax];
bool ok = false;
int head1, id1;
int head2, id2;
int id3;
int card[4];
void dfs(int x, int p = 0)
{
    sz[x] = 1;
    d[x] = d[p] + 1;
    for(auto e: adj[x])
    {
        if(e != p)
        {
            dfs(e, x);
            sz[x] += sz[e];
        }
    }
    if(ok)
        return;
    if(sz[x] >= a && n - sz[x] >= b)
    {
        ok = true;
        head1 = x, id1 = 1;
        head2 = p, id2 = 2;
        id3 = 3;
    }
    else if(sz[x] >= b && n - sz[x] >= a)
    {
        ok = true;
        head1 = x, id1 = 2;
        head2 = p, id2 = 1;
        id3 = 3;
    }
    else if(sz[x] >= a && n - sz[x] >= c)
    {
        ok = true;
        head1 = x, id1 = 1;
        head2 = p, id2 = 3;
        id3 = 2;
    }
    else if(sz[x] >= c && n - sz[x] >= a)
    {
        ok = true;
        head1 = x, id1 = 3;
        head2 = p, id2 = 1;
        id3 = 2;
    }
    else if(sz[x] >= b && n - sz[x] >= c)
    {
        ok = true;
        head1 = x, id1 = 2;
        head2 = p, id2 = 3;
        id3 = 1;
    }
    else if(sz[x] >= c && n -  sz[x] >= b)
    {
        ok = true;
        head1 = x, id1 = 3;
        head2 = p, id2 = 3;
        id3 = 1;
    }
}
int curid = 0;
int cnt = 0;
void dfs2(int x, int p)
{
    ans[x] = curid;
    cnt++;
    for(auto e: adj[x])
    {
        if(cnt == card[curid])
            return;
        if(e != p)
        {
            dfs2(e, x);
        }
    }
}
vi find_split(int N, int A, int B, int C, vi P, vi Q)
{
    n = N, a = A, b = B, c = C;
    m = P.size();
    for(int i =0 ; i < n; i++)
        adj[i].clear();
    card[1] = a, card[2] =  b, card[3] = c;
    for(int i = 0; i < m; i ++)
    {
        adj[P[i]].pb(Q[i]);
        adj[Q[i]].pb(P[i]);
    }
    ans.assign(n, 0);
    d[0] = -1;
    dfs(0, 0);
    if(!ok)
        return ans;
    curid = id1;
    dfs2(head1, head2);
    curid = id2;
    cnt = 0;
    dfs2(head2, head1);
    for(int i = 0 ; i < n ; i++)
    {
        if(ans[i] == 0)
            ans[i] = id3;
    }
    return ans;
}
/*
int32_t main()
{
    int N, M, A, B, C;
    cin >> N >> M >> A >> B >> C;
    vi P(M), Q(M);
    for(int i = 0; i < M; i++)
        cin >> P[i] >> Q[i];
    vi ANS = find_split(N, A, B, C, P, Q);
    for(auto e: ANS)
        cout << e << ' ';
}
*/

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36