제출 #253623

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
253623		TriPhan	Split the Attractions (IOI19_split)	C++14	0 / 100	41 ms	48072 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=sizeof(p);
    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);
    }
    dfs(1);
    vector<int> res;
    if (par[root]==0) {
        FOR(i,1,n)
            res.push_back(0);
        return res;
    }
    for (int v:a[root]) {
        if (n-sz[root] >= A[0].F) break;
        if (!lift[v]) continue;
        par[v]=lift[v];
        sz[root]-=sz[v];
    }
    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: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36