Submission #253682

#	Time	Username	Problem	Language	Result	Execution time	Memory
253682		TriPhan	Split the Attractions (IOI19_split)	C++14	40 / 100	198 ms	35444 KiB

split

#include <bits/stdc++.h>
#include <split.h>
#define TASK "SPLIT"
#define pb push_back
#define ii pair<int,int>
#define iii pair<ii,int>
#define ll long long
#define F first
#define S second
#define FOR(i, a, b) for (int i=a; i<=b; i++)
#define FOr(i, a, b) for (int i=a; i<b ; i++)
#define FOD(i, a, b) for (int i=a; i>=b; i--)
#define FOd(i, a, b) for (int i=a; i>b ; i--)
#define vi vector<int>
using namespace std;
 
const int N=(int)1e6+7;
const int MOD=(int)1e9+7;
const ll INF=(ll)1e18+7;
vector<int> a[N];
ii A[3];
int visit[N],par[N],sz[N],ans[N],lift[N];
int m,n,T,root;
void dfs(int u) {
    visit[u]=1;
    sz[u]=1;
    for (int v:a[u]) {
        if (visit[v]) {
            if (v!=par[u])
                lift[u]=v;
            continue;
        }
        par[v]=u;
        dfs(v);
        sz[u]+=sz[v];
    }
    if (sz[u] >= A[0].F && root==0)
        root=u;
}
 
void DFS(int u,int p) {
    if (A[T].F) {
        A[T].F--;
        ans[u]=A[T].S;
    }
    visit[u]=1;
    for (int v:a[u])
        if (v!=p && visit[v]==0)
            DFS(v,u);
}
vi find_split(int n, int aa, int b, int c, vi p, vi q) {
 
    m=p.size();
    A[0].F=aa;
    A[1].F=b;
    A[2].F=c;
    A[0].S=1;
    A[1].S=2;
    A[2].S=3;
    sort(A,A+3);
    FOR(i,0,m-1) {
        int u,v;
        u=p[i];
        v=q[i];
        ++u; ++v;
        a[u].pb(v);
        a[v].pb(u);
    }
    visit[1]=1;
    dfs(1);
    vector<int> res;
    if (par[root]==0) {
        FOR(i,1,n)
            res.push_back(0);
        return res;
    }
 
 
 
    queue<ii> Q;
    for (int v:a[root])
        Q.push({v,v});
    while (n-sz[root] < A[0].F && Q.size()) {
        ii z=Q.back();
        int v=z.F;
        int r=z.S;
        Q.pop();
        if (visit[r]==2) continue;
        if (lift[v]) {
            par[v]=lift[v];
            sz[root]-=sz[r];
            visit[r]=2;
            continue;
        }
        for (int u:a[v])
            if (par[u]==v)
              Q.push({u,r});
 
    }
    if (n-sz[root] < A[0].F) {
        FOR(i,1,n)
            res.push_back(0);
        return res;
    }
    FOR(i,1,n)
        a[i].clear();
    FOR(i,1,n)
        if (i!=root) {
            a[par[i]].push_back(i);
            if (par[i]!=0)
                a[i].push_back(par[i]);
        }
    FOR(i,1,n)
        visit[i]=0;
 
    if (sz[root]>=A[1].F) {
        T=1;
        DFS(root,0);
        T=0;
        DFS(par[root],0);
    }
    else {
        T=0;
        DFS(root,0);
        T=1;
        DFS(par[root],0);
    }
    FOR(i,1,n)
        if (!ans[i])
            ans[i]=A[2].S;
    FOR(i,1,n)
        res.push_back(ans[i]);
    return res;
}

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