Submission #991521

#	Time	Username	Problem	Language	Result	Execution time	Memory
991521		amine_aroua	Split the Attractions (IOI19_split)	C++17	40 / 100	50 ms	16988 KiB

split

#include <cstdio>
#include <cassert>
#include <bits/stdc++.h>
#define Int long long
#define fore(i , n) for(int i = 0 ; i<n;i++)
#define pb push_back
#define forn(i , x , y) for(int i = x ; i >= y; i--)
using namespace std;
vector<int> ans;
vector<vector<int>>adj;
vector<pair<int , int>> comp;
const int N = 2e5 + 10;
int sz[N];
bool found = 0;
void dfs_paint(int x , int p , int c , int &cnt)
{
    if(cnt <= 0)
        return ;
    ans[x] = c;
    cnt--;
    for(auto u : adj[x])
    {
        if(u == p)
            continue;
        dfs_paint(u , x , c , cnt);
    }
}
void dfs(int x , int p , int n)
{
    if(found)
        return ;
    sz[x] = 1;
    for(auto u : adj[x])
    {
        if(u == p)
            continue;
        if(found)
            return ;
        dfs(u , x , n);
        if(found)
            return ;
        sz[x]+=sz[u];
    }
    if(p != -1 && sz[x] >= comp[0].first && n - sz[x] >= comp[1].first)
    {
        dfs_paint(x ,p, comp[0].second , comp[0].first);
        dfs_paint(p , x , comp[1].second , comp[1].first);
        found = 1;
    }
    else if(p != -1 && sz[x] >= comp[1].first && n - sz[x] >= comp[0].first)
    {
        dfs_paint(x ,p, comp[1].second , comp[1].first);
        dfs_paint(p , x , comp[0].second , comp[0].first);
        found = 1;
    }
}
struct DSU
{
    vector<int> e;
    DSU(int n)
    {
        e.assign(n , -1);
    }
    int get(int x)
    {
        return (e[x] < 0 ? x : e[x] = get(e[x]));
    }
    bool unite(int u , int v)
    {
        u = get(u);
        v = get(v);
        if(u == v)
            return 0;
        if(e[u] > e[v])
            swap(u , v);
        e[u]+=e[v];
        e[v] = u;
        return 1;
    }
};
vector<int> find_split(int n, int _a , int _b , int _c , vector<int> p , vector<int> q)
{
    comp = {{_a , 1} , {_b , 2} , {_c , 3}};
    sort(comp.begin() , comp.end());
    ans.assign(n , 0);
    adj.assign(n , {});
    DSU dsu(n);
    int m = (int)p.size();
    fore(i , m)
    {
        if(dsu.unite(p[i] , q[i]))
        {
            adj[p[i]].pb(q[i]);
            adj[q[i]].pb(p[i]);
        }
    }
    dfs(0 , -1 , n);
    if(!found)
        return vector<int>(n, 0);
    fore(i , n)
    {
        if(!ans[i])
            ans[i] = comp[2].second;
    }
    return ans;
}
//int main() {
//    int n, m, A, B, C;
//    assert(5 == scanf("%d%d%d%d%d", &n, &m, &A, &B, &C));
//    vector<int> p(m), q(m);
//    for (int i=0; i<m; i++)
//        assert(2 == scanf("%d%d", &p[i], &q[i]));
//    fclose(stdin);
//
//    vector<int> result = find_split(n, A, B, C, p, q);
//
//    for (int i=0; i<(int)result.size(); i++)
//        printf("%s%d", ((i>0)?" ":""), result[i]);
//    printf("\n");
//    fclose(stdout);
//    return 0;
//}

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