제출 #1283816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283816		khanhphucscratch	Split the Attractions (IOI19_split)	C++20	7 / 100	2094 ms	18088 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> ad[100005];
int sz[100005], low[100005], num[100005], dfsc = 0;
int color[100005], deg[100005], xorval[100005];
bool visited[100005];
void dfs(int u, int par)
{
    visited[u] = 1; low[u] = num[u] = ++dfsc; sz[u] = 1;
    for(int v : ad[u]) if(par != v){
        if(visited[v] == 0){
            //cerr<<"A"<<u<<" "<<v<<endl;
            dfs(v, u); low[u] = min(low[u], low[v]); sz[u] += sz[v];
        }
        else low[u] = min(low[u], num[v]);
    }
}
void color_subtree(int u, int x)
{
    color[u] = x;
    for(int v : ad[u]) if(sz[v] < sz[u]) color_subtree(v, x);
}
int find_subtree(int u, int x)
{
    for(int v : ad[u]) if(sz[v] < sz[u] && sz[v] >= x) return find_subtree(v, x);
    return u;
}
void dfs_sigma(int u)
{
    visited[u] = 1;
    for(int v : ad[u]) if(visited[v] == 0 && color[v] == color[u]){
        deg[u]++; deg[v]++; xorval[u] ^= v; xorval[v] ^= u;
        dfs_sigma(v);
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
    for(int i = 0; i < p.size(); i++){
        int u = p[i], v = q[i];
        ad[u].push_back(v);
        ad[v].push_back(u);
    }
    vector<int> permu = {1, 2, 3};
    if(b > c){
        swap(b, c); swap(permu[1], permu[2]);
    }
    if(a > b){
        swap(a, b); swap(permu[0], permu[1]);
    }
    if(b > c){
        swap(b, c); swap(permu[1], permu[2]);
    }
    dfs(0, -1);
    int root = find_subtree(0, a);
    //Split everything to 2 parts
    color_subtree(0, 2); color_subtree(root, 1);
    int cursz = sz[root], outsz = n - sz[root];
    if(outsz < a){
        for(int v : ad[root]) if(sz[v] < sz[root] && low[v] < num[root]){
            color_subtree(v, 2);
            cursz -= sz[v]; outsz += sz[v];
            if(outsz >= a) break;
        }
    }
    if(outsz < a){
        vector<int> ans(n);
        return ans;
    }
    memset(visited, 0, sizeof(visited));
    for(int i = 0; i < n; i++) if(color[i] == 1){dfs_sigma(i); break;}
    for(int i = 0; i < n; i++) if(color[i] == 2){dfs_sigma(i); break;}
    int limcur = a, limout = b;
    if(outsz < b) swap(limcur, limout);
    queue<int> w;
    for(int i = 0; i < n; i++) if(deg[i] == 1 && color[i] == 1) w.push(i);
    while(cursz > limcur){
        int u = w.front(); w.pop(); color[u] = 3;
        xorval[xorval[u]] ^= u;
        if(--deg[xorval[u]] == 1) w.push(xorval[u]);
        cursz--;
    }
    while(w.size() > 0) w.pop();
    for(int i = 0; i < n; i++) if(deg[i] == 1 && color[i] == 2){
        w.push(i);
    }
    while(outsz > limout){
        int u = w.front(); w.pop(); color[u] = 3;
        xorval[xorval[u]] ^= u;
        if(--deg[xorval[u]] == 1) w.push(xorval[u]);
        outsz--;
    }
    vector<int> ans(n);
    for(int i = 0; i < n; i++) ans[i] = permu[color[i]-1];
    return ans;
}

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