Submission #143367

#	Time	Username	Problem	Language	Result	Execution time	Memory
143367		Bench0310	Split the Attractions (IOI19_split)	C++14	11 / 100	162 ms	23088 KiB

split

#include <bits/stdc++.h>

using namespace std;

int n;
const int N=100000;
vector<int> v[N];
vector<int> g[N];
vector<int> z[N];
vector<int> d;
vector<int> sub(N,0);
vector<int> id(N);
vector<bool> vis(N,0);
vector<int> res;

void dfs1(int a)
{
    sub[a]=1;
    for(int to:v[a])
    {
        if(sub[to]!=0) continue;
        g[a].push_back(to);
        g[to].push_back(a);
        dfs1(to);
        sub[a]+=sub[to];
    }
}

int get_centroid(int a,int p=-1)
{
    for(int to:g[a])
    {
        if(to!=p&&sub[to]>n/2) return get_centroid(to,a);
    }
    return a;
}

void dfs2(int a,int now)
{
    sub[a]=1;
    id[a]=now;
    for(int to:g[a])
    {
        if(sub[to]!=0) continue;
        if(now==-1) d.push_back(to);
        dfs2(to,(now!=-1?now:to));
        sub[a]+=sub[to];
    }
}

void solve_one(vector<int> src,int num,int t,int centroid)
{
    vector<bool> pos(n,0);
    for(int a:src) pos[a]=1;
    queue<int> q;
    q.push(src[0]);
    while(num>0)
    {
        int e=q.front();
        q.pop();
        res[e]=t;
        num--;
        for(int to:v[e]) if(to!=centroid&&pos[id[to]]==1&&res[to]==0) q.push(to);
    }
}

void solve_two(int num,int t,int centroid)
{
    res[centroid]=t;
    num--;
    queue<int> q;
    for(int to:g[centroid]) if(res[to]==0) q.push(to);
    while(num>0)
    {
        int e=q.front();
        q.pop();
        res[e]=t;
        num--;
        for(int to:g[e]) if(res[to]==0) q.push(to);
    }
}

void solve_three(int t)
{
    for(int i=0;i<n;i++) if(res[i]==0) res[i]=t;
}

vector<int> component(int src,int a)
{
    vector<int> comp;
    int cnt=0;
    vis[src]=1;
    queue<int> q;
    q.push(src);
    while(!q.empty())
    {
        int e=q.front();
        q.pop();
        cnt+=sub[e];
        comp.push_back(e);
        if(cnt>=a) break;
        for(int to:z[e])
        {
            if(vis[to]) continue;
            vis[to]=1;
            q.push(to);
        }
    }
    if(cnt>=a) return comp;
    else return {-1};
}

vector<int> find_split(int _n,int a,int b,int c,vector<int> ca,vector<int> cb)
{
    n=_n;
    res.resize(n,0);
    int m=ca.size();
    for(int i=0;i<m;i++)
    {
        v[ca[i]].push_back(cb[i]);
        v[cb[i]].push_back(ca[i]);
    }
    dfs1(0);
    int centroid=get_centroid(0);
    for(int i=0;i<n;i++) sub[i]=0;
    dfs2(centroid,-1);
    vector<pair<int,int>> abc={{a,1},{b,2},{c,3}};
    sort(abc.begin(),abc.end());
    for(int i=0;i<n;i++)
    {
        if(i!=centroid&&sub[i]>=abc[0].first)
        {
            solve_one({i},abc[0].first,abc[0].second,centroid);
            solve_two(abc[1].first,abc[1].second,centroid);
            solve_three(abc[2].second);
            return res;
        }
    }
    for(int i=0;i<m;i++)
    {
        if(ca[i]==centroid||cb[i]==centroid) continue;
        if(id[ca[i]]!=id[cb[i]])
        {
            z[id[ca[i]]].push_back(id[cb[i]]);
            z[id[cb[i]]].push_back(id[ca[i]]);
        }
    }
    for(int to:d)
    {
        if(vis[to]) continue;
        vector<int> comp=component(to,abc[0].first);
        if(comp[0]==-1) continue;
        solve_one(comp,abc[0].first,abc[0].second,centroid);
        solve_two(abc[1].first,abc[1].second,centroid);
        solve_three(abc[2].second);
        return res;
    }
    return res;
}

/*int main()
{
    vector<int> temp=find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5},{1, 2, 3, 4, 6, 8, 7, 7, 5, 6});
    for(int a:temp) cout << a << " ";
    return 0;
}
*/

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