oj.uz

답안 #925036

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925036 2024-02-10T13:31:21 Z hmm789 Split the Attractions (IOI19_split) C++14
40 / 100
 72 ms 23252 KB 
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000000000000
#define MOD 998244353

vector<int> adj[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 : adj[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 : adj[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;
    cout << "dfs " << x << " " << sz << " " << _c1 << " " << _c2 << endl;
    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);
}

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 < p.size(); i++) {
        adj[p[i]].push_back(q[i]);
        adj[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 : adj[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;
    }
    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:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0; i < p.size(); i++) {
      |                    ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10588 KB ok, correct split
2 Correct 2 ms 10516 KB ok, correct split
3 Correct 3 ms 10588 KB ok, correct split
4 Correct 3 ms 10532 KB ok, correct split
5 Correct 3 ms 10588 KB ok, correct split
6 Correct 2 ms 10588 KB ok, correct split
7 Correct 59 ms 23120 KB ok, correct split
8 Correct 54 ms 21324 KB ok, correct split
9 Correct 54 ms 20556 KB ok, correct split
10 Correct 52 ms 23252 KB ok, correct split
11 Correct 60 ms 23248 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 10588 KB ok, correct split
2 Correct 2 ms 10588 KB ok, correct split
3 Correct 3 ms 10588 KB ok, correct split
4 Correct 67 ms 20960 KB ok, correct split
5 Correct 47 ms 16980 KB ok, correct split
6 Correct 53 ms 23252 KB ok, correct split
7 Correct 54 ms 21072 KB ok, correct split
8 Correct 72 ms 19404 KB ok, correct split
9 Correct 48 ms 17228 KB ok, correct split
10 Correct 49 ms 20376 KB ok, correct split
11 Correct 46 ms 19984 KB ok, correct split
12 Correct 44 ms 20056 KB ok, correct split

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 10588 KB ok, correct split
2 Correct 50 ms 17072 KB ok, correct split
3 Correct 20 ms 13144 KB ok, correct split
4 Correct 2 ms 10588 KB ok, correct split
5 Correct 50 ms 19280 KB ok, correct split
6 Correct 52 ms 18880 KB ok, correct split
7 Correct 57 ms 18956 KB ok, correct split
8 Correct 53 ms 20044 KB ok, correct split
9 Correct 53 ms 18760 KB ok, correct split
10 Correct 16 ms 12760 KB ok, no valid answer
11 Correct 23 ms 13984 KB ok, no valid answer
12 Correct 61 ms 18768 KB ok, no valid answer
13 Correct 50 ms 17236 KB ok, no valid answer
14 Correct 44 ms 20048 KB ok, no valid answer

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10588 KB ok, correct split
2 Correct 2 ms 10588 KB ok, no valid answer
3 Correct 3 ms 10588 KB ok, correct split
4 Correct 3 ms 10584 KB ok, correct split
5 Correct 3 ms 10588 KB ok, correct split
6 Correct 4 ms 10528 KB ok, correct split
7 Correct 3 ms 10588 KB ok, correct split
8 Correct 3 ms 10588 KB ok, correct split
9 Correct 4 ms 10844 KB ok, correct split
10 Correct 4 ms 10704 KB ok, correct split
11 Correct 3 ms 10584 KB ok, correct split
12 Incorrect 5 ms 10676 KB invalid split: #1=800, #2=1596, #3=5
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10588 KB ok, correct split
2 Correct 2 ms 10516 KB ok, correct split
3 Correct 3 ms 10588 KB ok, correct split
4 Correct 3 ms 10532 KB ok, correct split
5 Correct 3 ms 10588 KB ok, correct split
6 Correct 2 ms 10588 KB ok, correct split
7 Correct 59 ms 23120 KB ok, correct split
8 Correct 54 ms 21324 KB ok, correct split
9 Correct 54 ms 20556 KB ok, correct split
10 Correct 52 ms 23252 KB ok, correct split
11 Correct 60 ms 23248 KB ok, correct split
12 Correct 3 ms 10588 KB ok, correct split
13 Correct 2 ms 10588 KB ok, correct split
14 Correct 3 ms 10588 KB ok, correct split
15 Correct 67 ms 20960 KB ok, correct split
16 Correct 47 ms 16980 KB ok, correct split
17 Correct 53 ms 23252 KB ok, correct split
18 Correct 54 ms 21072 KB ok, correct split
19 Correct 72 ms 19404 KB ok, correct split
20 Correct 48 ms 17228 KB ok, correct split
21 Correct 49 ms 20376 KB ok, correct split
22 Correct 46 ms 19984 KB ok, correct split
23 Correct 44 ms 20056 KB ok, correct split
24 Correct 3 ms 10588 KB ok, correct split
25 Correct 50 ms 17072 KB ok, correct split
26 Correct 20 ms 13144 KB ok, correct split
27 Correct 2 ms 10588 KB ok, correct split
28 Correct 50 ms 19280 KB ok, correct split
29 Correct 52 ms 18880 KB ok, correct split
30 Correct 57 ms 18956 KB ok, correct split
31 Correct 53 ms 20044 KB ok, correct split
32 Correct 53 ms 18760 KB ok, correct split
33 Correct 16 ms 12760 KB ok, no valid answer
34 Correct 23 ms 13984 KB ok, no valid answer
35 Correct 61 ms 18768 KB ok, no valid answer
36 Correct 50 ms 17236 KB ok, no valid answer
37 Correct 44 ms 20048 KB ok, no valid answer
38 Correct 2 ms 10588 KB ok, correct split
39 Correct 2 ms 10588 KB ok, no valid answer
40 Correct 3 ms 10588 KB ok, correct split
41 Correct 3 ms 10584 KB ok, correct split
42 Correct 3 ms 10588 KB ok, correct split
43 Correct 4 ms 10528 KB ok, correct split
44 Correct 3 ms 10588 KB ok, correct split
45 Correct 3 ms 10588 KB ok, correct split
46 Correct 4 ms 10844 KB ok, correct split
47 Correct 4 ms 10704 KB ok, correct split
48 Correct 3 ms 10584 KB ok, correct split
49 Incorrect 5 ms 10676 KB invalid split: #1=800, #2=1596, #3=5
50 Halted 0 ms 0 KB -