oj.uz

Submission #313900

# Submission time Handle Problem Language Result Execution time Memory
313900 2020-10-17T09:05:17 Z nikatamliani Split the Attractions (IOI19_split) C++14
18 / 100
 183 ms 26360 KB 
#include <bits/stdc++.h>
#define vi vector < int >
#include "split.h"
using namespace std;
const int N = 2e5 + 10;
int in[N], out[N], sub[N], P[N];
int countA, countB, countC, aa = 1, bb = 2, cc = 3;
bool vis[N];
int timer = 0;
vi edges[N], redges[N], ans;
void dfs(int x, int p) {
    if(vis[x]) return;
    vis[x] = sub[x] = 1; 
    for(int to : edges[x]) {
        if(to != p) {
            if(!vis[to]) {
                P[to] = x;
                dfs(to, x);
                sub[x] += sub[to];
                redges[to].push_back(x);
                redges[x].push_back(to);
            }
        }
    }
}
void reroot(int x, int p) {
    in[x] = ++timer;
    sub[x] = 1;
    for(int to : redges[x]) {
        if(to != p) {
            reroot(to, x);
            sub[x] += sub[to];
        }
    }
    out[x] = ++timer;
}
void find_answer(int x, int p, int v) {
    if(in[v] <= in[x] && out[v] >= out[x]) {
        if(countA > 0) {
            ans[x] = aa;
            --countA;
        } 
    } else {
        if(countB > 0) {
            ans[x] = bb;
            --countB;
        }
    }
    for(int to : redges[x]) {
        if(to != p) {
            find_answer(to, x, v);
        }
    }
}
int find_best(int x, int p) {
    int a = countA, c = countC;
    for(int to : redges[x]) {
        if(to != p) {
            if(sub[to] >= a && sub[to] <= c + a) {
                return x;
            } 
        } else {
            if(sub[0] - sub[to] >= a && sub[0] - sub[to] <= c + a) {
                return x;
            }
        }
    }
    for(int to : redges[x]) {
        if(to != p && sub[to] > c + a) {
            return find_best(to, x);
        }
    }
    return -1;
}
vi find_split(int n, int a, int b, int c, vi p, vi q) {
    ans.resize(n);
    if(a > b) swap(a, b), swap(aa, bb);
    if(b > c) swap(b, c), swap(bb, cc);
    if(a > b) swap(a, b), swap(aa, bb);
    countA = a, countB = b, countC = c;
    for(int i = 0; i < q.size(); ++i) {
        edges[q[i]].push_back(p[i]);
        edges[p[i]].push_back(q[i]);
    }
    dfs(0, -1);
    int root = find_best(0, -1), from = -1;
    if(root == -1) return ans;
    reroot(root, -1);
    for(int x : redges[root]) {
        if(sub[x] >= a && sub[x] <= c + a) {
            from = x;
        }
    }
    find_answer(root, -1, from);
    for(int i = 0; i < n; ++i) if(ans[i] == 0) ans[i] = cc;
    return ans;
}

Compilation message

split.cpp: In function 'void dfs(int, int)':
split.cpp:13:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   13 |     vis[x] = sub[x] = 1;
      |              ~~~~~~~^~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = 0; i < q.size(); ++i) {
      |                    ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB ok, correct split
2 Correct 7 ms 9728 KB ok, correct split
3 Correct 7 ms 9728 KB ok, correct split
4 Correct 7 ms 9728 KB ok, correct split
5 Correct 7 ms 9728 KB ok, correct split
6 Correct 7 ms 9728 KB ok, correct split
7 Correct 139 ms 25976 KB ok, correct split
8 Correct 135 ms 24184 KB ok, correct split
9 Correct 135 ms 23644 KB ok, correct split
10 Correct 137 ms 26232 KB ok, correct split
11 Correct 141 ms 26360 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB ok, correct split
2 Correct 7 ms 9728 KB ok, correct split
3 Correct 7 ms 9728 KB ok, correct split
4 Correct 169 ms 23928 KB ok, correct split
5 Correct 126 ms 20216 KB ok, correct split
6 Correct 149 ms 26360 KB ok, correct split
7 Correct 138 ms 24056 KB ok, correct split
8 Correct 183 ms 22008 KB ok, correct split
9 Correct 128 ms 20088 KB ok, correct split
10 Correct 87 ms 20848 KB ok, correct split
11 Correct 89 ms 20848 KB ok, correct split
12 Correct 91 ms 20848 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9728 KB ok, correct split
2 Incorrect 112 ms 19448 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB ok, correct split
2 Correct 7 ms 9728 KB ok, no valid answer
3 Correct 7 ms 9728 KB ok, correct split
4 Correct 7 ms 9728 KB ok, correct split
5 Correct 7 ms 9728 KB ok, correct split
6 Correct 7 ms 9728 KB ok, correct split
7 Correct 7 ms 9728 KB ok, correct split
8 Correct 7 ms 9728 KB ok, correct split
9 Correct 9 ms 10112 KB ok, correct split
10 Correct 9 ms 9984 KB ok, correct split
11 Correct 7 ms 9728 KB ok, correct split
12 Correct 9 ms 10112 KB ok, correct split
13 Correct 7 ms 9728 KB ok, correct split
14 Correct 7 ms 9728 KB ok, correct split
15 Correct 7 ms 9728 KB ok, correct split
16 Correct 7 ms 9728 KB ok, correct split
17 Correct 7 ms 9728 KB ok, correct split
18 Correct 7 ms 9728 KB ok, correct split
19 Correct 7 ms 9856 KB ok, correct split
20 Correct 8 ms 9856 KB ok, correct split
21 Correct 9 ms 9984 KB ok, correct split
22 Incorrect 9 ms 9984 KB jury found a solution, contestant did not
23 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB ok, correct split
2 Correct 7 ms 9728 KB ok, correct split
3 Correct 7 ms 9728 KB ok, correct split
4 Correct 7 ms 9728 KB ok, correct split
5 Correct 7 ms 9728 KB ok, correct split
6 Correct 7 ms 9728 KB ok, correct split
7 Correct 139 ms 25976 KB ok, correct split
8 Correct 135 ms 24184 KB ok, correct split
9 Correct 135 ms 23644 KB ok, correct split
10 Correct 137 ms 26232 KB ok, correct split
11 Correct 141 ms 26360 KB ok, correct split
12 Correct 7 ms 9728 KB ok, correct split
13 Correct 7 ms 9728 KB ok, correct split
14 Correct 7 ms 9728 KB ok, correct split
15 Correct 169 ms 23928 KB ok, correct split
16 Correct 126 ms 20216 KB ok, correct split
17 Correct 149 ms 26360 KB ok, correct split
18 Correct 138 ms 24056 KB ok, correct split
19 Correct 183 ms 22008 KB ok, correct split
20 Correct 128 ms 20088 KB ok, correct split
21 Correct 87 ms 20848 KB ok, correct split
22 Correct 89 ms 20848 KB ok, correct split
23 Correct 91 ms 20848 KB ok, correct split
24 Correct 8 ms 9728 KB ok, correct split
25 Incorrect 112 ms 19448 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -