oj.uz

Submission #343863

# Submission time Handle Problem Language Result Execution time Memory
343863 2021-01-04T15:41:58 Z 79brue Split the Attractions (IOI19_split) C++14
0 / 100
 77 ms 8684 KB 
#include <bits/stdc++.h>
#include "split.h"

using namespace std;

typedef long long ll;

int n, m, a, b, c;
vector<int> link[100002];
int idx[4];
vector<int> ret;
int cnt;
int DP[100002];
int tmp=-1;

int dfs(int x, int p = -1){
    DP[x] = 1;
    for(auto y: link[x]){
        if(p==y) continue;
        DP[x] += dfs(y, x);
    }
    if(min(DP[x], n - DP[x]) >= a && max(DP[x], n - DP[x]) >= b){
        tmp = x;
    }
    return DP[x];
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
    m = (int)p.size();
    n = _n, a = _a, b = _b, c = _c;
    if(m != n-1) exit(1);

    vector<pair<int, int> > v {make_pair(a, 1), make_pair(b, 2), make_pair(c, 3)};
    sort(v.begin(), v.end());
    a = v[0].first, b = v[1].first, c = v[2].first;
    idx[1] = v[0].second, idx[2] = v[1].second, idx[3] = v[2].second;

    for(int i=0; i<m; i++){
        link[p[i]].push_back(q[i]);
        link[q[i]].push_back(p[i]);
    }
    ret.resize(n);

    dfs(0);
    if(tmp == -1) return ret;

    int rootNum, childNum;
    if(DP[tmp] >= a && n-DP[tmp] >= b) rootNum = 2, childNum = 1;
    else rootNum = 1, childNum = 2;

    queue<int> tq; tq.push(0);
    for(int cnt=0; cnt<((DP[tmp] >= a && n-DP[tmp] >= b) ? b : a); cnt++){\
        int tmp = tq.front(); tq.pop();
        ret[tmp] = rootNum;
        for(auto y: link[tmp]){
            if(y == tmp || ret[y]) continue;
            tq.push(y);
        }
    }
    while(!tq.empty()) tq.pop();
    tq.push(tmp);
    for(int cnt=0; cnt<((DP[tmp] >= a && n-DP[tmp] >= b) ? a : b); cnt++){
        if(tq.empty()) return ret;
        int tmp = tq.front(); tq.pop();
        ret[tmp] = childNum;
        for(auto y: link[tmp]){
            if(ret[y]) continue;
            tq.push(y);
        }
    }
    for(int i=0; i<n; i++) if(!ret[i]) ret[i] = 3;
    for(int i=0; i<n; i++) ret[i] = idx[ret[i]];
    return ret;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB ok, correct split
2 Runtime error 2 ms 2668 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB ok, correct split
2 Runtime error 2 ms 2668 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB ok, correct split
2 Incorrect 77 ms 8684 KB answer contains both zero and positive values
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 2668 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB ok, correct split
2 Runtime error 2 ms 2668 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -