Submission #253763

#	Time	Username	Problem	Language	Result	Execution time	Memory
253763		minhgiang1032	Split the Attractions (IOI19_split)	C++14	40 / 100	147 ms	15480 KiB

split

#include <bits/stdc++.h>
//#include <split.h>

#define fu(_i,_a,_b) for (int _i=_a; _i<=_b; _i++)
#define fd(_i,_a,_b) for (int _i=_a; _i>=_b; _i--)

#define pb push_back
#define ALL(VecS) VecS.begin(),VecS.end()
#define x first
#define y second

#define task "split"

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<int,ll> il;
typedef pair<ll,int> li;
typedef vector <int> vi;

const int N=100005;
const ll BASE=10000;

int n, m, aa, par[N], depth[N], s[N], R=1, mrk[N], cnt, c1, ans[N], ca, cb, Prev[N];
ii A[4];
vi G[N];

void dfs(int u)
{
    s[u]=1;
    for (int v: G[u])
        if (!depth[v])
    {
        depth[v]=depth[u]+1;
        Prev[v]=u;
        //cout << u << " " << v << '\n';
        dfs(v);
        s[u]+=s[v];
    }
}

void DFS(int u)
{
    for (int v: G[u])
        if (depth[v]==depth[u]+1)
    {
        if (s[v]>=aa)
        {
            if (depth[v]>depth[R]) R=v;
            DFS(v);
        }
    }
}

void DFS1(int u)
{
    par[u]=1;
    for (int v: G[u])
        if (depth[v]==depth[u]+1)
    {
        DFS1(v);
        for (int k: G[v])
            if (par[k]==0) {mrk[v]=1; break;}
    }
}

void Mk(int u)
{
    par[u]=0;
    for (int v: G[u])
        if (depth[v]==depth[u]+1)
        Mk(v);
}

void Hsgi(int u)
{
    //cout << u << ' ';
    if (n-s[R]>=aa) return;

    if (mrk[u]==1 && s[R]-s[u]>=aa)
        {
            s[R]-=s[u]; Mk(u);
            while (Prev[u]!=R) {u=Prev[u]; par[u]=0; s[R]--;}
            return;
        }

    for (int v: G[u])
        if (depth[v]==depth[u]+1 && par[v]==1) {if (!par[u]) break; Hsgi(v);}
}

int visit[N];

void pra(int u,int clr, int z)
{
    if (ca==0) return;
    if (par[u]==clr) ans[u]=z;
    visit[u]=1;
    ca--;
    for (int v: G[u])
        if (!visit[v])
    {
        if (par[v]==clr) pra(v,clr,z);
    }
}

vi find_split(int n, int a, int b, int c, vi p, vi q)
{
    fu(i,1,n) par[i]=0,ans[i]=0;
    A[1].x=a; A[2].x=b; A[3].x=c;

    A[1].y=1; A[2].y=2; A[3].y=3;
    sort(A+1,A+4);
    aa=min({A[1].x,A[2].x,A[3].x});

    int u,v;
    m=p.size();
    fu(i,1,m)
    {
        u=p[i-1]+1,v=q[i-1]+1;
        //u++; v++;
        G[u].pb(v);
        G[v].pb(u);
    }

    depth[1]=1;
    depth[0]=0;

    dfs(1);
    DFS(1);
    DFS1(R);
    Hsgi(R);

    if (n-s[R]<aa) fu(i,1,n) ans[i]=0;
    else
    {
        if (n-s[R]>=A[2].x) {ca=A[2].x; pra(1,0,A[2].y); ca=A[1].x; pra(R,1,A[1].y);}
        else { ca=A[2].x; pra(R,1,A[2].y); ca=A[1].x; pra(1,0,A[1].y);}
        fu(i,1,n) if (!ans[i]) ans[i]=A[3].y;
        //fu(i,1,n) cout << ans[i] << " ";
    }
    vi Ans(0);
    fu(i,1,n) Ans.pb(ans[i]);
    return Ans;
}

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