제출 #1292470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292470		MMihalev	Split the Attractions (IOI19_split)	C++20	0 / 100	764 ms	1114112 KiB

split

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include "split.h"
using namespace std;
const int MAX_N=3e5+5;
vector<int>g[MAX_N];
int col[MAX_N];
int deg[MAX_N];
int A,B;
int whA,whB;
int parent[MAX_N];
int sz[MAX_N];
void dfs(int u,int par)
{
    //sz[u]=1;
    for(int v:g[u])
    {
        if(v==par)continue;
        //deg[u]++;
        //deg[v]++;
        //parent[v]=u;
        dfs(v,u);
        //sz[u]+=sz[v];
    }
}
int ban=-1;
void colour(int u,int color)
{
    if(u==-1)while(1);
    col[u]=color;
    for(int v:g[u])
    {
        if(col[v]==color or v==ban)continue;
        colour(v,color);
    }
}
vector<int>ans;
vector<pair<int,int>>shit;
int N;
void solve()
{
    queue<int>bfs;
    int cntwhA=0;
    for(int i=0;i<N;i++)
    {
        if(col[i]==whA)
        {
            cntwhA++;
            if(deg[i]==1)bfs.push(i);
        }
    }
    int toremove=cntwhA-A;
    while(bfs.size()>0 && toremove>0)
    {
        int u=bfs.front();
        bfs.pop();
        toremove--;
        col[u]=shit[2].second;

        for(int v:g[u])
        {
            if(col[v]==whA)
            {
                deg[v]--;
                if(deg[v]==1)bfs.push(v);
            }
        }
    }

    while(bfs.size()>0)bfs.pop();
    int cntwhB=0;
    for(int i=0;i<N;i++)
    {
        if(col[i]==whB)
        {
            cntwhB++;
            if(deg[i]==1)bfs.push(i);
        }
    }
    toremove=cntwhB-B;
    while(bfs.size()>0 && toremove>0)
    {
        int u=bfs.front();
        bfs.pop();
        toremove--;
        col[u]=shit[2].second;

        for(int v:g[u])
        {
            if(col[v]==whB)
            {
                deg[v]--;
                if(deg[v]==1)bfs.push(v);
            }
        }
    }
    //B

    for(int i=0;i<N;i++)ans[i]=col[i];
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
    N=n;

    ans.resize(n);
    for(int i=0;i<n;i++)
    {
        col[i]=0;
        g[i].clear();
        deg[i]=0;
    }
    shit.clear();

    shit.push_back({a,1});shit.push_back({b,2});shit.push_back({c,3});
    sort(shit.begin(),shit.end());

    A=shit[0].first;whA=shit[0].second;
    B=shit[1].first;whB=shit[1].second;

    for(int i=0;i<p.size() && i<q.size();i++)
    {
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
    }

    parent[0]=-1;
    dfs(0,-1);
    return ans;

    vector<pair<int,int>>subtrees;
    for(int i=0;i<n;i++)
    {
        subtrees.clear();
        int all=1;
        for(int u:g[i])
        {
            if(u==parent[i])continue;
            subtrees.push_back({sz[u],u});
            all+=sz[u];
        }
        if(i>0)subtrees.push_back({n-all,parent[i]});
        sort(subtrees.begin(),subtrees.end());

        int firstA=-1,firstB=-1;
        for(auto [s,u]:subtrees)
        {
            if(s>=A && firstA==-1)
            {
                firstA=u;
            }
            if(s>=B && firstB==-1)
            {
                firstB=u;
            }
        }

        if(firstA==-1)continue;

        if(n-sz[firstA]>=B)
        {
            colour(0,whB);
            ban=i;
            colour(firstA,whA);
            solve();
            return ans;
        }
        else if(firstB!=-1 && n-sz[firstB]>=A)
        {
            colour(0,whA);
            ban=i;
            colour(firstB,whB);
            solve();
            return ans;
        }
        else continue;
    }

    return ans;
}

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