제출 #1285875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285875		trandangquang	Split the Attractions (IOI19_split)	C++20	29 / 100	232 ms	36520 KiB

split

//#include"split.h"
#include<bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int MAXN=101010;

int n;
vector<int> adj[MAXN];
ii a[3];
map<ii,int>mp;

void init(int N, int A, int B, int C, vector<int> p, vector<int> q){
    n=N;
    rep(i,sz(p)){
        if(p[i]<q[i])swap(p[i],q[i]);
        if(mp.find({p[i],q[i]})!=mp.end())continue;
        mp[{p[i],q[i]}]=1;

        adj[p[i]].eb(q[i]);
        adj[q[i]].eb(p[i]);
    }
    /// a<=b && b<=c
    a[0]={A,1}; a[1]={B,2}; a[2]={C,3};
    sort(a,a+3);
    /// wait have to change something here
}

/**
    thuat toan: bay gio xet moi dinh thap nhat ma co gtri >= a
    -> xet phan con lai coi >= a hay khong
    neu co, lay gia tri nho hon lm a, gtri lon hon lm b

    neu khong, lay cac goc trong cay con xong push cho ngoai sao cho o trong vx con >= a dinh
    cuoi cung, lay nhung dinh c co deg = 1 va cu the ...
**/

int tin[MAXN],tout[MAXN],low[MAXN],par[MAXN],sz[MAXN],tour[MAXN],tim;
vector<int> tree[MAXN];
bool isOpt[MAXN];
void dfs(int u, int p=-1){
    par[u]=p; sz[u]=1;
    tin[u]=low[u]=++tim;
    tour[tim]=u;
    int mxc=0;
    for(int v:adj[u]) if(v!=p){
        if(!tin[v]){
            dfs(v,u);
            tree[u].eb(v);
            sz[u]+=sz[v];
            maxi(mxc,sz[v]);
            low[u]=min(low[u],low[v]);
        } else{
            low[u]=min(low[u],tin[v]);
        }
    }
    tout[u]=tim;
    if(sz[u]>=a[0].fi && mxc<a[0].fi) isOpt[u]=1;//,cout<<u<<'\n';
}
void buildTree(){
    dfs(0);
}

bool used[MAXN];
vector<int> setA,setB;
bool isSatisfied(){
    rep(u,n) if(isOpt[u]){
        int out=n-sz[u], in=sz[u];

        vector<int> trans;
        for(int v:tree[u]){
            if(low[v]<tin[u] && in-sz[v]>=a[0].fi){
                in-=sz[v];
                out+=sz[v];
                trans.eb(v);
            }
        }

        if(in>=a[0].fi && out>=a[0].fi){
            foru(i,1,tin[u]-1) setB.eb(tour[i]);
            foru(i,tout[u]+1,n) setB.eb(tour[i]);
            for(int v:trans){
                foru(i,tin[v],tout[v]) setB.eb(tour[i]),used[i]=1;
            }
            foru(i,tin[u],tout[u]) if(!used[i]) setA.eb(tour[i]);
            return true;
        }
    }
    return false;
}

int mark[MAXN]; bool omit[MAXN];
int deg[MAXN],parD[MAXN]; bool isIn[MAXN];
int find(int x){
    return parD[x]==x?x:parD[x]=find(parD[x]);
}
bool unite(int x, int y){
    x=find(x); y=find(y);
    if(x!=y){
        parD[y]=x;
        return true;
    }
    return false;
}
void hehe(vector<int> arr, int num, int id){
//    cerr<<num _ id<<'\n';
    memset(isIn,0,sizeof(isIn));
    memset(deg,0,sizeof(deg));
    iota(parD,parD+n,0);

    for(int i:arr) isIn[i]=1;
    for(int i:arr){
        for(int j:adj[i]) if(isIn[j]){
            if(unite(i,j)){
                ++deg[i]; ++deg[j];
            }
        }
    }

    vector<int> vt;
    for(int i:arr) if(deg[i]==1) vt.eb(i);

    foru(i,1,sz(arr)-num){
        int u=vt.back();vt.pop_back();
        omit[u]=true;
        for(int v:adj[u]) if(isIn[v]){
            deg[v]--;
            if(deg[v]==1) vt.eb(v);
        }
    }

    for(int i:arr) if(!omit[i]) mark[i]=id;
}

vector<int> hihi(){
    vector<int> res(n);
    rep(i,n) res[i]=mark[i];
    return res;
}

vector<int> answer(){
    if(!isSatisfied()){
        return hihi();
    }
    if(sz(setA)>sz(setB)) swap(setA,setB);
    hehe(setA,a[0].fi,a[0].se);
    hehe(setB,a[1].fi,a[1].se);
    rep(i,n) if(mark[i]==0) mark[i]=a[2].se;
    return hihi();
}

vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q){
    init(N,A,B,C,p,q);
    buildTree();
//    cout<<isSatisfied();
    return answer();
}

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