Submission #415594

#	Time	Username	Problem	Language	Result	Execution time	Memory
415594		xyz	Split the Attractions (IOI19_split)	C++17	18 / 100	99 ms	12952 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);
}

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);
    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: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36