oj.uz

Submission #925052

# Submission time Handle Problem Language Result Execution time Memory
925052 2024-02-10T14:12:05 Z hmm789 Split the Attractions (IOI19_split) C++17
40 / 100
 94 ms 30104 KB 
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000000000000
#define MOD 998244353

vector<int> adj[100000], adj3[100000], grpv[100001];
set<pair<int, tuple<int, int, int>>> adj2[100000];
vector<int> path, res;
vector<pair<int, int>> t1;
int sz[100000], grp[100001], d, e, c1 = -1, c2 = -1, cnt;
bool v[100000];

int size(int x, int g) {
    v[x] = 1; sz[x] = 1; grp[x] = g;
    if(g != -1) grpv[g].push_back(x);
    for(int i : adj3[x]) if(!v[i]) {
        if(g == -1) sz[x] += size(i, i);
        else sz[x] += size(i, g);
    }
    return sz[x];
}

int centroid(int x, int n) {
    v[x] = 1;
    for(int i : adj3[x]) if(!v[i] && sz[i] > n/2) return centroid(i, n);
    return x;
}

bool dfs(int x, int sz, int _c1, int _c2) {
    v[x] = 1;
    if(sz >= d) {
        c1 = _c1; c2 = _c2;
        path.push_back(x);
        return true;
    }
    for(auto i : adj2[x]) if(!v[i.first]) {
        if(dfs(i.first, sz+get<0>(i.second), get<1>(i.second), get<2>(i.second))) {
            path.push_back(x);
            return true;
        }
    }
    return false;
}

void dfs2(int x) {
    v[x] = 1;
    if(cnt == 0) return;
    res[x] = t1[0].second;
    cnt--;
    for(int i : adj[x]) if(!v[i] && grp[i] == grp[x]) dfs2(i);
}

void dfs3(int x) {
    if(cnt == 0) return;
    res[x] = t1[1].second;
    cnt--;
    for(int i : adj[x]) if(res[i] == 0) dfs3(i);
}

int up[100000];
int root(int x) {
    if(up[x] == x) return x;
    else return up[x] = root(up[x]);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    for(int i = 0; i < n; i++) res.push_back(0);
    for(int i = 0; i < n; i++) up[i] = i;
    for(int i = 0; i < p.size(); i++) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
        if(root(p[i]) == root(q[i])) continue;
        int x = root(p[i]), y = root(q[i]);
        up[x] = y;
        adj3[p[i]].push_back(q[i]);
        adj3[q[i]].push_back(p[i]);
    }
    t1 = {{a, 1}, {b, 2}, {c, 3}};
    sort(t1.begin(), t1.end());
    d = t1[0].first; e = t1[1].first;
    size(0, n);
    memset(v, 0, sizeof(v));
    int cen = centroid(0, n);
    memset(v, 0, sizeof(v));
    size(cen, -1);
    for(int i : adj3[cen]) if(sz[i] >= d) {
        memset(v, 0, sizeof(v));
        cnt = d;
        dfs2(i);
        cnt = e;
        dfs3(cen);
        for(int j = 0; j < n; j++) if(res[j] == 0) res[j] = t1[2].second;
        return res;
    }
    for(int i : adj3[cen]) assert(sz[i] == grpv[i].size());
    for(int i = 0; i < n; i++) {
        for(int j : adj[i]) {
            if(grp[i] == -1 || grp[j] == -1) continue;
            if(grp[i] == grp[j]) continue;
            auto it = adj2[grp[i]].lower_bound({grp[j], {0, 0, 0}});
            if(it != adj2[grp[i]].end() && it->first == grp[j]) continue;
            adj2[grp[i]].insert({grp[j], {sz[grp[j]], i, j}});
            adj2[grp[j]].insert({grp[i], {sz[grp[i]], j, i}});
        }
    }
    memset(v, 0, sizeof(v));
    for(int i : adj3[cen]) if(!v[i]) {
        if(dfs(i, sz[i], -1, -1)) break;
    }
    if(c1 == -1) return res;
    cnt = d;
    for(int i = 1; i < path.size(); i++) {
        for(int j : grpv[path[i]]) {
            res[j] = t1[0].second;
            cnt--;
        }
    }
    memset(v, 0, sizeof(v));
    dfs2(c2);
    cnt = e;
    dfs3(cen);
    for(int i = 0; i < n; i++) if(res[i] == 0) res[i] = t1[2].second;
    return res;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = 0; i < p.size(); i++) {
      |                    ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from split.cpp:1:
split.cpp:95:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i : adj3[cen]) assert(sz[i] == grpv[i].size());
      |                                   ~~~~~~^~~~~~~~~~~~~~~~~
split.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i = 1; i < path.size(); i++) {
      |                    ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13148 KB ok, correct split
2 Correct 4 ms 13148 KB ok, correct split
3 Correct 3 ms 13148 KB ok, correct split
4 Correct 3 ms 13148 KB ok, correct split
5 Correct 3 ms 13148 KB ok, correct split
6 Correct 3 ms 13148 KB ok, correct split
7 Correct 82 ms 30024 KB ok, correct split
8 Correct 68 ms 28236 KB ok, correct split
9 Correct 75 ms 27724 KB ok, correct split
10 Correct 76 ms 30028 KB ok, correct split
11 Correct 77 ms 29252 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13148 KB ok, correct split
2 Correct 3 ms 13148 KB ok, correct split
3 Correct 3 ms 13288 KB ok, correct split
4 Correct 84 ms 25640 KB ok, correct split
5 Correct 81 ms 24484 KB ok, correct split
6 Correct 73 ms 30104 KB ok, correct split
7 Correct 72 ms 28236 KB ok, correct split
8 Correct 94 ms 27208 KB ok, correct split
9 Correct 64 ms 24136 KB ok, correct split
10 Correct 63 ms 27020 KB ok, correct split
11 Correct 57 ms 26956 KB ok, correct split
12 Correct 61 ms 27348 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13148 KB ok, correct split
2 Correct 71 ms 23216 KB ok, correct split
3 Correct 26 ms 17752 KB ok, correct split
4 Correct 3 ms 13144 KB ok, correct split
5 Correct 75 ms 26024 KB ok, correct split
6 Correct 78 ms 26016 KB ok, correct split
7 Correct 70 ms 25928 KB ok, correct split
8 Correct 77 ms 26700 KB ok, correct split
9 Correct 72 ms 25984 KB ok, correct split
10 Correct 23 ms 16848 KB ok, no valid answer
11 Correct 32 ms 18872 KB ok, no valid answer
12 Correct 66 ms 26192 KB ok, no valid answer
13 Correct 71 ms 24396 KB ok, no valid answer
14 Correct 63 ms 27468 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13148 KB ok, correct split
2 Correct 3 ms 13144 KB ok, no valid answer
3 Correct 3 ms 13148 KB ok, correct split
4 Correct 3 ms 13148 KB ok, correct split
5 Correct 3 ms 13284 KB ok, correct split
6 Correct 3 ms 13148 KB ok, correct split
7 Correct 4 ms 13264 KB ok, correct split
8 Correct 4 ms 13144 KB ok, correct split
9 Correct 4 ms 13404 KB ok, correct split
10 Correct 5 ms 13520 KB ok, correct split
11 Correct 3 ms 13148 KB ok, correct split
12 Incorrect 5 ms 13788 KB jury found a solution, contestant did not
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13148 KB ok, correct split
2 Correct 4 ms 13148 KB ok, correct split
3 Correct 3 ms 13148 KB ok, correct split
4 Correct 3 ms 13148 KB ok, correct split
5 Correct 3 ms 13148 KB ok, correct split
6 Correct 3 ms 13148 KB ok, correct split
7 Correct 82 ms 30024 KB ok, correct split
8 Correct 68 ms 28236 KB ok, correct split
9 Correct 75 ms 27724 KB ok, correct split
10 Correct 76 ms 30028 KB ok, correct split
11 Correct 77 ms 29252 KB ok, correct split
12 Correct 3 ms 13148 KB ok, correct split
13 Correct 3 ms 13148 KB ok, correct split
14 Correct 3 ms 13288 KB ok, correct split
15 Correct 84 ms 25640 KB ok, correct split
16 Correct 81 ms 24484 KB ok, correct split
17 Correct 73 ms 30104 KB ok, correct split
18 Correct 72 ms 28236 KB ok, correct split
19 Correct 94 ms 27208 KB ok, correct split
20 Correct 64 ms 24136 KB ok, correct split
21 Correct 63 ms 27020 KB ok, correct split
22 Correct 57 ms 26956 KB ok, correct split
23 Correct 61 ms 27348 KB ok, correct split
24 Correct 3 ms 13148 KB ok, correct split
25 Correct 71 ms 23216 KB ok, correct split
26 Correct 26 ms 17752 KB ok, correct split
27 Correct 3 ms 13144 KB ok, correct split
28 Correct 75 ms 26024 KB ok, correct split
29 Correct 78 ms 26016 KB ok, correct split
30 Correct 70 ms 25928 KB ok, correct split
31 Correct 77 ms 26700 KB ok, correct split
32 Correct 72 ms 25984 KB ok, correct split
33 Correct 23 ms 16848 KB ok, no valid answer
34 Correct 32 ms 18872 KB ok, no valid answer
35 Correct 66 ms 26192 KB ok, no valid answer
36 Correct 71 ms 24396 KB ok, no valid answer
37 Correct 63 ms 27468 KB ok, no valid answer
38 Correct 3 ms 13148 KB ok, correct split
39 Correct 3 ms 13144 KB ok, no valid answer
40 Correct 3 ms 13148 KB ok, correct split
41 Correct 3 ms 13148 KB ok, correct split
42 Correct 3 ms 13284 KB ok, correct split
43 Correct 3 ms 13148 KB ok, correct split
44 Correct 4 ms 13264 KB ok, correct split
45 Correct 4 ms 13144 KB ok, correct split
46 Correct 4 ms 13404 KB ok, correct split
47 Correct 5 ms 13520 KB ok, correct split
48 Correct 3 ms 13148 KB ok, correct split
49 Incorrect 5 ms 13788 KB jury found a solution, contestant did not
50 Halted 0 ms 0 KB -