Submission #253609

#	Time	Username	Problem	Language	Result	Execution time	Memory
253609		minhgiang1032	Split the Attractions (IOI19_split)	C++14	0 / 100	3 ms	2688 KiB

split

#include <bits/stdc++.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, a, par[N], depth[N], s[N], R=1, mrk[N], b, cnt, c1, ans[N], ca, cb;
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;
        //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]>=a)
        {
            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;
    s[R]--;
    b++;
    for (int v: G[u])
        if (depth[v]==depth[u]+1)
        Mk(v);
}

void Hsgi(int u)
{
    //cout << u << ' ';
    if (b>=a) return;
    if (mrk[u]==1 && s[R]-s[u]>=a) {Mk(u); return;}

    for (int v: G[u])
        if (depth[v]==depth[u]+1) Hsgi(v);
}

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

vi find_split(int n, int AA, int BB, int CC, vi p, vi q)
{
    fu(i,1,n) par[i]=0;
    A[1].x=AA; A[2].x=BB; A[3].x=CC;

    A[1].y=1; A[2].y=2; A[3].y=3;
    sort(A+1,A+4);
    a=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);
    b=n-s[R];
    Hsgi(R);

    if (b<a) fu(i,1,n) ans[i]=0;
    else
    {
        if (b>=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;
    fu(i,1,n) Ans.pb(ans[i]);
    return Ans;
}

/*int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);

    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);

    //cin >> n >> m;
    fu(i,1,n) par[i]=0;
    cin >> A[1].x >> A[2].x >> A[3].x;

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

    int u,v;
    fu(i,1,m)
    {
        cin >> u >> v;
        u++; v++;
        G[u].pb(v);
        G[v].pb(u);
    }

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

    dfs(1);
    DFS(1);
    DFS1(R);
    b=n-s[R];
    Hsgi(R);

    if (b<a) fu(i,1,n) cout << "0" << ' ';
    else
    {
        if (b>=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] << " ";
    }
    return 0;
}*/

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