Submission #1201326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201326		Kaang	Split the Attractions (IOI19_split)	C++20	40 / 100	86 ms	25416 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using pll = pair<ll, ll>;
using vi = vector<int>;
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define sz(v) ((int)(v).size())
#define all(v) v.begin(), v.end()
using namespace std;
int dpt[100001],sz[100001],sp[100001],cnt,num[100001],pr[100001],vst[100001],cnta,cntb,ta,tb,tp;
vector <int> v[100001],g[100001];
priority_queue <pii> pq;
vector <int> ans;
void dfs(int node,int par)
{
    cnt++;
    num[node]=cnt;
    sp[node]=cnt;
    sz[node]=1;
    pr[node]=par;
    for(auto cur:v[node])
    {
        if(cur==par)
            continue;
        else if(dpt[cur]==0)
        {
            g[node].push_back(cur);
            dpt[cur]=dpt[node]+1;
            dfs(cur,node);
            sp[node]=min(sp[node],sp[cur]);
            sz[node]+=sz[cur];
        }
        else
        {
            sp[node]=min(sp[node],num[cur]);
        }
    }
    return ;
}
void fdfs(int node,int f)
{
    if(vst[node])
        return;
    else
    {
        vst[node]=f;
        for(auto cur:v[node])
            fdfs(cur,f);
    }
}
void adfs(int node,int f)
{
    if(vst[node]!=f||ans[node]!=0)
        return;
    else
    {
        if(cnta<ta&&vst[node]==f)
            ans[node]=f,cnta++;
        else if(vst[node]==f)
            return;
        for(auto cur:v[node])
            adfs(cur,f);

    }
}
void bdfs(int node,int f)
{
    if(vst[node]!=f||ans[node]!=0)
        return;
    else
    {
        if(cntb<tb&&vst[node]==f)
            ans[node]=f,cntb++;
        else if(vst[node]==f)
            return;
        for(auto cur:v[node])
            bdfs(cur,f);

    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int m=p.size();
    ans.clear();
    ans.resize(n,0);
    if(a<=b&&b<=c)
        tp=1;
    else if(a<=c&&c<b)
        tp=2;
    else if(c<a&&a<=b)
        tp=3;
    else if(b<a&&a<=c)
        tp=4;
    else if(b<=c&&c<a)
        tp=5;
    else if(c<b&&b<a)
        tp=6;
    if(a>b)
        swap(a,b);
    if(a>c)
        swap(a,c);
    if(b>c)
        swap(b,c);
    ta=a,tb=b;
    for(int i=0;i<m;i++)
    {
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
    }
    dpt[0]=1;
    dfs(0,-1);
    int dt1=0,dt2=0;//dt1이면 해 존재, dt2면 해 구성 불가, 판별필요 없음
    for(int i=0;i<n;i++)
    {
        int mx1=0,mx2=0,lft=n-1;
        for(int cur:g[i])
        {
            if(sp[cur]>=num[i])
            {
                int szcur=sz[cur];
                lft-=szcur;
                if(szcur>=mx1)
                {
                    mx2=mx1;
                    mx1=szcur;
                }
                else if(szcur<mx1&&szcur>=mx2)
                {
                    mx2=szcur;
                }
            }
        }
        if(lft>=mx1)
        {
            mx2=mx1;
            mx1=lft;
        }
        else if(lft<mx1&&lft>=mx2)
        {
            mx2=lft;
        }
        if(mx1>=b&&n-mx1>=a)
        {
            dt1=1;
            vst[i]=1;
            if(lft==mx1)
            {
                fdfs(pr[i],2);
                for(int cur:g[i])
                {
                    fdfs(cur,1);
                }
            }
            else
            {
                for(int cur:g[i])
                {
                    if(sz[cur]==mx1)
                    {
                        fdfs(cur,2);
                        break;
                    }
                }
                for(int cur:g[i])
                {
                    fdfs(cur,1);
                }
                if(pr[i]!=-1)
                    fdfs(pr[i],1);
            }
            break;
        }
        else if(mx1>=b&&n-mx1<a)
            continue;
        else if(mx1<b&&mx2<a)
        {
            if(mx1<a)
            {
                dt2=1;
                break;
            }
            else
            {
                dt1=1;
                vst[i]=2;
                if(lft==mx1)
                {
                    fdfs(pr[i],1);
                    for(int cur:g[i])
                    {
                        fdfs(cur,2);
                    }
                    int nu=0;
                    for(int j=0;j<n;j++)
                    {
                        if(vst[j]==0)
                        nu++;
                    }
                }
                else
                {
                    for(int cur:g[i])
                    {
                        if(sz[cur]==mx1)
                        {
                            fdfs(cur,1);
                            break;
                        }
                    }
                    for(int cur:g[i])
                    {
                        fdfs(cur,2);
                    }
                    if(pr[i]!=-1)
                    fdfs(pr[i],2);
                }
                break;
            }

        }
        else if(mx1<b&&mx2>=a)
        {
            dt1=1;
            vst[i]=2;
            if(lft==mx2)
            {
                fdfs(pr[i],1);
                for(int cur:g[i])
                {
                    fdfs(cur,2);
                }
            }
            else
            {
                for(int cur:g[i])
                {
                    if(sz[cur]==mx2)
                    {
                        fdfs(cur,1);
                        break;
                    }
                }
                for(int cur:g[i])
                {
                    fdfs(cur,2);
                }
                if(pr[i]!=-1)
                    fdfs(pr[i],2);
            }
            break;
        }
    }
    if(dt2)
    {
        return ans;
    }
    else if(dt1)
    {
        for(int i=0;i<n;i++)
        {
            if(vst[i]==1)
                adfs(i,1);
            else if(vst[i]==2)
                bdfs(i,2);
        }
        for(int i=0;i<n;i++)
        {
            if(ans[i]==0)
                ans[i]=3;
        }
        for(int i=0;i<n;i++)
        {
            if(tp==1)
                ans[i]=ans[i];
            else if(tp==2)
            {
                if(ans[i]==2)
                    ans[i]=3;
                else if(ans[i]==3)
                    ans[i]=2;
            }
            else if(tp==3)
            {
                if(ans[i]==1)
                    ans[i]=3;
                else if(ans[i]==2)
                    ans[i]=1;
                else if(ans[i]==3)
                    ans[i]=2;
            }
            else if(tp==4)
            {
                if(ans[i]==1)
                    ans[i]=2;
                else if(ans[i]==2)
                    ans[i]=1;
                else
                    ans[i]=3;
            }
            else if(tp==5)
            {
                if(ans[i]==1)
                    ans[i]=2;
                else if(ans[i]==2)
                    ans[i]=3;
                else
                    ans[i]=1;
            }
            else
            {
                if(ans[i]==1)
                    ans[i]=3;
                else if(ans[i]==2)
                    ans[i]=2;
                else
                    ans[i]=1;
            }
        }
        return ans;
    }
    else
    {
        int cura=0;
        pq.push({1,0});
        while(cura<a)
        {
            int node=pq.top().se;
            pq.pop();
            if(vst[node]==0)
            {
                vst[node]=1;
                cura++;
                int lft=n-1;
                for(int cur:g[node])
                {
                    if(sp[cur]>=num[node])
                    {
                        lft-=sz[cur];
                        if(sz[cur]<a)
                        {
                            fdfs(cur,1);
                            cura+=sz[cur];
                        }
                    }
                }
                if(lft<a&&pr[node]!=-1)
                {
                    fdfs(pr[node],1);
                    cura+=lft;
                }
                for(int cur:v[node])
                {
                    if(vst[cur]==0)
                        pq.push({dpt[cur],cur});
                }
                if(pr[node]!=-1&&vst[pr[node]]==0)
                    pq.push({dpt[pr[node]],pr[node]});
            }
        }
        for(int i=0;i<n;i++)
        {
            if(vst[i]!=1)
                vst[i]=2;
        }
        for(int i=0;i<n;i++)
        {
            if(vst[i]==1)
                adfs(i,1);
            else
                bdfs(i,2);
        }
        for(int i=0;i<n;i++)
        {
            if(ans[i]==0)
                ans[i]=3;
        }
        for(int i=0;i<n;i++)
        {
            if(tp==1)
                ans[i]=ans[i];
            else if(tp==2)
            {
                if(ans[i]==2)
                    ans[i]=3;
                else if(ans[i]==3)
                    ans[i]=2;
            }
            else if(tp==3)
            {
                if(ans[i]==1)
                    ans[i]=3;
                else if(ans[i]==2)
                    ans[i]=1;
                else if(ans[i]==3)
                    ans[i]=2;
            }
            else if(tp==4)
            {
                if(ans[i]==1)
                    ans[i]=2;
                else if(ans[i]==2)
                    ans[i]=1;
                else
                    ans[i]=3;
            }
            else if(tp==5)
            {
                if(ans[i]==1)
                    ans[i]=2;
                else if(ans[i]==2)
                    ans[i]=3;
                else
                    ans[i]=1;
            }
            else
            {
                if(ans[i]==1)
                    ans[i]=3;
                else if(ans[i]==2)
                    ans[i]=2;
                else
                    ans[i]=1;
            }
        }
        return ans;
    }
}

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