oj.uz

Submission #69805

# Submission time Handle Problem Language Result Execution time Memory
69805 2018-08-21T14:22:08 Z aquablitz11 Simurgh (IOI17_simurgh) C++14
51 / 100
 1382 ms 5164 KB 
#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
 
using pii = pair<int, int>;
const int N = 510;
const int M = N*(N-1)/2;
const int LIM = 30000;
 
vector<pii> G[N];
vector<int> E;
 
int par[N];
int root(int u) {
    if (par[u] == u) return u;
    return par[u] = root(par[u]);
}
bool merge(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) return false;
    par[u] = v;
    return true;
}
 
bool tree[M];
int ans[M];
 
vector<int> find_roads(int n, vector<int> U, vector<int> V)
{
    int cntq = 0;
 
    int m = U.size();
    iota(par, par+n, 0);
    fill(ans, ans+m, -1);
    for (int i = 0; i < m; ++i) {
        int u = U[i], v = V[i];
        if (merge(u, v)) {
            G[u].emplace_back(v, i);
            G[v].emplace_back(u, i);
            E.push_back(i);
            tree[i] = true;
        }
    }
    if (++cntq == LIM) assert(false);
    int defcnt = count_common_roads(E);
    for (int i = 0; i < m; ++i) if (!tree[i]) {
        int u = U[i], v = V[i];
        vector<int> par(n, -1);
        vector<int> ix(n, -1);
        par[u] = u;
        queue<int> Q;
        Q.push(u);
        while (!Q.empty()) {
            int s = Q.front(); Q.pop();
            if (s == v) break;
            for (auto t : G[s]) if (par[t.first] == -1) {
                par[t.first] = s;
                ix[t.first] = t.second;
                Q.push(t.first);
            }
        }
        map<int, bool> inp;
        vector<int> path;
        int s = v;
        do {
            inp[ix[s]] = true;
            path.push_back(ix[s]);
            s = par[s];
        } while (s != u);
 
        int typ = -1; // not -1 = found determined
        for (auto e : path) {
            if (ans[e] != -1) {
                typ = e;
                break;
            }
        }
        vector<int> other;
        for (auto e : E) {
            if (!inp[e])
                other.push_back(e);
        }
        if (typ == -1) {
            ans[i] = 0;
            for (auto e : path) {
                vector<int> q(other.begin(), other.end());
                for (auto p : path) if (p != e)
                    q.push_back(p);
                q.push_back(i);
                if (++cntq == LIM) assert(false);
                int cnt = count_common_roads(q);
                if (cnt-defcnt == 1)
                    ans[e] = 0, ans[i] = 1;
                else if (cnt-defcnt == -1)
                    ans[i] = 0, ans[e] = 1;
            }
            if (ans[i] == -1) ans[i] = 0;
            for (auto e : path) if (ans[e] == -1)
                ans[e] = ans[i];
        } else {
            vector<int> q(other.begin(), other.end());
            for (auto e : path) if (e != typ)
                q.push_back(e);
            q.push_back(i);
            if (++cntq == LIM) assert(false);
            int cnt = count_common_roads(q);
            ans[i] = ans[typ]+(cnt-defcnt);
            for (auto e : path) if (ans[e] == -1) {
                q = vector<int>(other.begin(), other.end());
                for (auto p : path) if (p != e) q.push_back(p);
                q.push_back(i);
                if (++cntq == LIM) assert(false);
                int cnt = count_common_roads(q);
                if (cnt-defcnt == 1) ans[e] = 0;
                else if (cnt-defcnt == -1) ans[e] = 1;
                else ans[e] = ans[i];
            }
        }
    }
    vector<int> ret;
    ret.reserve(n-1);
    for (int i = 0; i < m; ++i) {
        if (ans[i] != 0)
            ret.push_back(i);
    }
    return ret;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 488 KB correct
3 Correct 3 ms 508 KB correct
4 Correct 3 ms 544 KB correct
5 Correct 2 ms 628 KB correct
6 Correct 3 ms 628 KB correct
7 Correct 2 ms 636 KB correct
8 Correct 2 ms 636 KB correct
9 Correct 3 ms 636 KB correct
10 Correct 3 ms 748 KB correct
11 Correct 3 ms 748 KB correct
12 Correct 2 ms 748 KB correct
13 Correct 2 ms 748 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 488 KB correct
3 Correct 3 ms 508 KB correct
4 Correct 3 ms 544 KB correct
5 Correct 2 ms 628 KB correct
6 Correct 3 ms 628 KB correct
7 Correct 2 ms 636 KB correct
8 Correct 2 ms 636 KB correct
9 Correct 3 ms 636 KB correct
10 Correct 3 ms 748 KB correct
11 Correct 3 ms 748 KB correct
12 Correct 2 ms 748 KB correct
13 Correct 2 ms 748 KB correct
14 Correct 14 ms 748 KB correct
15 Correct 13 ms 748 KB correct
16 Correct 12 ms 748 KB correct
17 Correct 11 ms 748 KB correct
18 Correct 6 ms 748 KB correct
19 Correct 14 ms 760 KB correct
20 Correct 11 ms 848 KB correct
21 Correct 10 ms 848 KB correct
22 Correct 8 ms 848 KB correct
23 Correct 9 ms 868 KB correct
24 Correct 13 ms 872 KB correct
25 Correct 3 ms 976 KB correct
26 Correct 7 ms 976 KB correct
27 Correct 7 ms 976 KB correct
28 Correct 5 ms 976 KB correct
29 Correct 3 ms 976 KB correct
30 Correct 8 ms 976 KB correct
31 Correct 8 ms 976 KB correct
32 Correct 9 ms 976 KB correct
33 Correct 8 ms 976 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 488 KB correct
3 Correct 3 ms 508 KB correct
4 Correct 3 ms 544 KB correct
5 Correct 2 ms 628 KB correct
6 Correct 3 ms 628 KB correct
7 Correct 2 ms 636 KB correct
8 Correct 2 ms 636 KB correct
9 Correct 3 ms 636 KB correct
10 Correct 3 ms 748 KB correct
11 Correct 3 ms 748 KB correct
12 Correct 2 ms 748 KB correct
13 Correct 2 ms 748 KB correct
14 Correct 14 ms 748 KB correct
15 Correct 13 ms 748 KB correct
16 Correct 12 ms 748 KB correct
17 Correct 11 ms 748 KB correct
18 Correct 6 ms 748 KB correct
19 Correct 14 ms 760 KB correct
20 Correct 11 ms 848 KB correct
21 Correct 10 ms 848 KB correct
22 Correct 8 ms 848 KB correct
23 Correct 9 ms 868 KB correct
24 Correct 13 ms 872 KB correct
25 Correct 3 ms 976 KB correct
26 Correct 7 ms 976 KB correct
27 Correct 7 ms 976 KB correct
28 Correct 5 ms 976 KB correct
29 Correct 3 ms 976 KB correct
30 Correct 8 ms 976 KB correct
31 Correct 8 ms 976 KB correct
32 Correct 9 ms 976 KB correct
33 Correct 8 ms 976 KB correct
34 Correct 1310 ms 1684 KB correct
35 Correct 1310 ms 2108 KB correct
36 Correct 884 ms 2108 KB correct
37 Correct 63 ms 2108 KB correct
38 Correct 1318 ms 2340 KB correct
39 Correct 1041 ms 2340 KB correct
40 Correct 832 ms 2440 KB correct
41 Correct 1382 ms 2876 KB correct
42 Correct 1342 ms 3044 KB correct
43 Correct 667 ms 3044 KB correct
44 Correct 511 ms 3044 KB correct
45 Correct 624 ms 3064 KB correct
46 Correct 419 ms 3064 KB correct
47 Correct 153 ms 3064 KB correct
48 Correct 8 ms 3064 KB correct
49 Correct 45 ms 3064 KB correct
50 Correct 180 ms 3064 KB correct
51 Correct 588 ms 3324 KB correct
52 Correct 554 ms 3324 KB correct
53 Correct 411 ms 3384 KB correct
54 Correct 698 ms 3588 KB correct
55 Correct 617 ms 3696 KB correct
56 Correct 609 ms 3928 KB correct
57 Correct 655 ms 3928 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB correct
2 Correct 2 ms 3928 KB correct
3 Incorrect 973 ms 5164 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 488 KB correct
3 Correct 3 ms 508 KB correct
4 Correct 3 ms 544 KB correct
5 Correct 2 ms 628 KB correct
6 Correct 3 ms 628 KB correct
7 Correct 2 ms 636 KB correct
8 Correct 2 ms 636 KB correct
9 Correct 3 ms 636 KB correct
10 Correct 3 ms 748 KB correct
11 Correct 3 ms 748 KB correct
12 Correct 2 ms 748 KB correct
13 Correct 2 ms 748 KB correct
14 Correct 14 ms 748 KB correct
15 Correct 13 ms 748 KB correct
16 Correct 12 ms 748 KB correct
17 Correct 11 ms 748 KB correct
18 Correct 6 ms 748 KB correct
19 Correct 14 ms 760 KB correct
20 Correct 11 ms 848 KB correct
21 Correct 10 ms 848 KB correct
22 Correct 8 ms 848 KB correct
23 Correct 9 ms 868 KB correct
24 Correct 13 ms 872 KB correct
25 Correct 3 ms 976 KB correct
26 Correct 7 ms 976 KB correct
27 Correct 7 ms 976 KB correct
28 Correct 5 ms 976 KB correct
29 Correct 3 ms 976 KB correct
30 Correct 8 ms 976 KB correct
31 Correct 8 ms 976 KB correct
32 Correct 9 ms 976 KB correct
33 Correct 8 ms 976 KB correct
34 Correct 1310 ms 1684 KB correct
35 Correct 1310 ms 2108 KB correct
36 Correct 884 ms 2108 KB correct
37 Correct 63 ms 2108 KB correct
38 Correct 1318 ms 2340 KB correct
39 Correct 1041 ms 2340 KB correct
40 Correct 832 ms 2440 KB correct
41 Correct 1382 ms 2876 KB correct
42 Correct 1342 ms 3044 KB correct
43 Correct 667 ms 3044 KB correct
44 Correct 511 ms 3044 KB correct
45 Correct 624 ms 3064 KB correct
46 Correct 419 ms 3064 KB correct
47 Correct 153 ms 3064 KB correct
48 Correct 8 ms 3064 KB correct
49 Correct 45 ms 3064 KB correct
50 Correct 180 ms 3064 KB correct
51 Correct 588 ms 3324 KB correct
52 Correct 554 ms 3324 KB correct
53 Correct 411 ms 3384 KB correct
54 Correct 698 ms 3588 KB correct
55 Correct 617 ms 3696 KB correct
56 Correct 609 ms 3928 KB correct
57 Correct 655 ms 3928 KB correct
58 Correct 2 ms 3928 KB correct
59 Correct 2 ms 3928 KB correct
60 Incorrect 973 ms 5164 KB WA in grader: NO
61 Halted 0 ms 0 KB -