제출 #415605

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415605		xyz	Split the Attractions (IOI19_split)	C++17	7 / 100	115 ms	17420 KiB

split

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

const int N = 1e5 + 10;
vector<int> g[N];
int A[3], B[3], sub[N], n, Max[4], have[4];
vector<int> result, bad;

void dfs(int v, int x){
    if(have[B[x]] >= Max[B[x]])
        return;
    result[v] = B[x];
    have[B[x]] ++;
    for(int u : g[v])
        if(!result[u])
            dfs(u, x);
}


void dfs1(int v, int p){
    sub[v] = 1;
    for(int x : g[v]){
        if(x != p){
            dfs1(x, v);
            sub[v] += sub[x];
        }
    }
}

void paint(int v, int p, int w){
    if(have[B[w]] >= Max[B[w]])
        w = 2;
    have[B[w]] ++;
    result[v] = B[w];
    for(int x : g[v]){
        if(x != p){
            paint(x, v, w);
        }
    }
}

bool dfs2(int v, int p){
    for(int x : g[v]){
        if(x == p)
            continue;
        if(sub[x] >= A[0] && n - sub[x] >= A[1]){
            paint(x, v, 0);
            paint(v, x, 1);
            return true;
        }
    }
    for(int x : g[v]){
        if(x == p)
            continue;
        bool _b = dfs2(x, v);
        if(_b) return true;
    }
    return false;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
    int m = p.size();
    n = N;
    for(int i = 0; i < m; i ++){
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
    }
    A[0] = a, B[0] = 1, Max[1] = a;
    A[1] = b, B[1] = 2, Max[2] = b;
    A[2] = c, B[2] = 3, Max[3] = c;
    if(A[2] < A[1]){
        swap(A[2], A[1]);
        swap(B[2], B[1]);
    }
    if(A[2] < A[0]){
        swap(A[2], A[0]);
        swap(B[2], B[0]);
    }
    if(A[0] < A[1]){
        swap(A[0], A[1]);
        swap(B[0], B[1]);
    }
//    for(int i = 0; i < 3; i ++)
//        cout << A[i] << " " << B[i] << endl;
//    for(int i = 1; i <= 3; i ++)
//        cout << i << " : " << Max[i] << endl;
    result.resize(n);
    bad.resize(n);
    if(m == n - 1){
//        cout << "tree !!!" << endl;
        dfs1(0, 0);
        dfs2(0, 0);
    }else{
        dfs(0, 0);
        for(int i = 0; i < n; i ++){
            if(!result[i]){
                dfs(i, 1);
                break;
            }
        }
        for(int i = 0; i < n; i ++)
            if(!result[i])
                result[i] = B[2], have[B[2]] ++;
    }
    if(have[1] != Max[1] || have[2] != Max[2] || have[3] != Max[3])
        return bad;
    return result;
}

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