Submission #1279368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279368		hainam2k9	Split the Attractions (IOI19_split)	C++20	100 / 100	104 ms	29484 KiB

split

#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 1e5+5;
const string NAME = "";
int n,m,sz[MAXN],depth[MAXN],par[MAXN],mindepth[MAXN],val[MAXN],vis[MAXN];
bool vis2[MAXN];
pair<int,int> a[5];
vector<int> adj[MAXN],rs;
int dfs2(int u, int x, int k){
    if(k==0) return 0;
    val[u]=x, --k;
    for(int& v : adj[u])
        if(vis[v]==2&&!vis2[v]&&val[v]==0) k=dfs2(v,x,k);
    return k;
}
int dfs3(int u, int x, int k){
    if(k==0) return 0;
    val[u]=x, --k;
    for(int& v : adj[u])
        if(val[v]==0) k=dfs3(v,x,k);
    return k;
}
bool dfs(int u){
    if(!rs.empty()) return 1;
    vector<int> child;
    bool ok=0;
    sz[u]=vis[u]=1;
    mindepth[u]=depth[u];
    for(int& v : adj[u]){
        if(!vis[v]){
            par[v]=u, depth[v]=depth[u]+1, ok|=dfs(v), sz[u]+=sz[v];
            if(mindepth[v]<depth[u]) child.pb(v);
            mindepth[u]=min(mindepth[u],mindepth[v]);
        }
        else mindepth[u]=min(mindepth[u],depth[v]);
    }
    vis[u]=2;
    if(!ok&&sz[u]>=a[1].fi){
        vector<int> tmp;
        int SZ=sz[u];
        while(n-SZ<a[1].fi&&!child.empty()) SZ-=sz[child.back()], tmp.pb(child.back()), vis2[child.back()]=1, child.pob();
        if(n-SZ>=a[1].fi){
            if(SZ>=a[2].fi){
                dfs2(u,a[2].se,a[2].fi);
                dfs3(1,a[1].se,a[1].fi);
            }else{
                dfs2(u,a[1].se,a[1].fi);
                dfs3(1,a[2].se,a[2].fi);
            }
            for(int i = 1; i<=n; ++i){
                if(val[i]==0) rs.pb(a[3].se);
                else rs.pb(val[i]);
            }
        }
        while(!tmp.empty()) vis2[tmp.back()]=0, tmp.pob();
        return 1;
    }
    return ok;
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q){
    n=N, m=sz(p);
    a[1].fi=A, a[2].fi=B, a[3].fi=C;
    for(int i = 1; i<=3; ++i)
        a[i].se=i;
    sort(a+1,a+4);
    for(int i = 0; i<m; ++i){
        int x=p[i], y=q[i];
        ++x, ++y;
        adj[x].pb(y), adj[y].pb(x);
    }
    dfs(1);
    if(rs.empty()){
        for(int i = 1; i<=n; ++i)
            rs.pb(0);
    }
    return rs;
}

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