oj.uz

Submission #137370

# Submission time Handle Problem Language Result Execution time Memory
137370 2019-07-27T14:19:55 Z fredbr Simurgh (IOI17_simurgh) C++17
30 / 100
 240 ms 2552 KB 
#include "simurgh.h"

#include <bits/stdc++.h>

using namespace std;

struct Dsu {
    vector<int> pai, w;
    int comp;

    Dsu(int n) : pai(n), w(n, 1), comp(n) {
        iota(pai.begin(), pai.end(), 0);
    }

    int find(int x) {
        if (x == pai[x]) return x;
        return pai[x] = find(pai[x]);
    }

    void join(int x, int y) {
        x = find(x), y = find(y);

        if (w[x] < w[y]) swap(x, y);
        pai[y] = x;
        w[x] += w[y];
        comp--;
    }

    bool con(int x, int y) {
        return find(x) == find(y);
    }
};

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    int m = u.size();
    vector<int> golden(m);

    for (int vtx = 0; vtx < n; vtx++) {
        vector<pair<int, int>> num;
        vector<int> r;

        Dsu dsu(n);
        for (int i = 0; i < m; i++) {
            if (u[i] == vtx or v[i] == vtx) continue;

            if (!dsu.con(u[i], v[i])) {
                dsu.join(u[i], v[i]);
                r.push_back(i);
            }
        }

        for (int i = 0; i < m; i++) {
            if (u[i] == vtx or v[i] == vtx) {
                if (!dsu.con(u[i], v[i]) and dsu.comp == 2) {
                    r.push_back(i);
                    num.push_back({i, count_common_roads(r)});
                    r.pop_back();
                }
            }
        }

        int maxi = 0;
        for (auto const& p : num) {
            maxi = max(maxi, p.second);
        }

        for (auto const& p : num) {
            if (p.second == maxi) {
                golden[p.first] = 1;
            }
        }
    }

    vector<int> r;
    Dsu dsu(n);
    for (int i = 0; i < m; i++) {
        if (golden[i]) {
            r.push_back(i);
            dsu.join(u[i], v[i]);
        }
    }

    for (int i = 0; i < m; i++) {
        if (!golden[i] and !dsu.con(u[i], v[i])) {
            golden[i] = 1;
            dsu.join(u[i], v[i]);
            r.push_back(i);
        }
    }

    return r;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 256 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 376 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 256 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 256 KB correct
10 Correct 2 ms 256 KB correct
11 Correct 2 ms 256 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 256 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 256 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 376 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 256 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 256 KB correct
10 Correct 2 ms 256 KB correct
11 Correct 2 ms 256 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 256 KB correct
14 Correct 7 ms 376 KB correct
15 Correct 6 ms 376 KB correct
16 Correct 6 ms 500 KB correct
17 Correct 6 ms 376 KB correct
18 Correct 4 ms 504 KB correct
19 Correct 6 ms 376 KB correct
20 Correct 6 ms 376 KB correct
21 Correct 5 ms 376 KB correct
22 Correct 4 ms 380 KB correct
23 Correct 4 ms 376 KB correct
24 Correct 4 ms 256 KB correct
25 Correct 2 ms 252 KB correct
26 Correct 4 ms 256 KB correct
27 Correct 4 ms 376 KB correct
28 Correct 3 ms 376 KB correct
29 Correct 3 ms 256 KB correct
30 Correct 4 ms 256 KB correct
31 Correct 4 ms 376 KB correct
32 Correct 4 ms 256 KB correct
33 Correct 4 ms 376 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 256 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 376 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 256 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 256 KB correct
10 Correct 2 ms 256 KB correct
11 Correct 2 ms 256 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 256 KB correct
14 Correct 7 ms 376 KB correct
15 Correct 6 ms 376 KB correct
16 Correct 6 ms 500 KB correct
17 Correct 6 ms 376 KB correct
18 Correct 4 ms 504 KB correct
19 Correct 6 ms 376 KB correct
20 Correct 6 ms 376 KB correct
21 Correct 5 ms 376 KB correct
22 Correct 4 ms 380 KB correct
23 Correct 4 ms 376 KB correct
24 Correct 4 ms 256 KB correct
25 Correct 2 ms 252 KB correct
26 Correct 4 ms 256 KB correct
27 Correct 4 ms 376 KB correct
28 Correct 3 ms 376 KB correct
29 Correct 3 ms 256 KB correct
30 Correct 4 ms 256 KB correct
31 Correct 4 ms 376 KB correct
32 Correct 4 ms 256 KB correct
33 Correct 4 ms 376 KB correct
34 Incorrect 240 ms 1132 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB correct
2 Correct 2 ms 252 KB correct
3 Incorrect 185 ms 2552 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 256 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 376 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 256 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 256 KB correct
10 Correct 2 ms 256 KB correct
11 Correct 2 ms 256 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 256 KB correct
14 Correct 7 ms 376 KB correct
15 Correct 6 ms 376 KB correct
16 Correct 6 ms 500 KB correct
17 Correct 6 ms 376 KB correct
18 Correct 4 ms 504 KB correct
19 Correct 6 ms 376 KB correct
20 Correct 6 ms 376 KB correct
21 Correct 5 ms 376 KB correct
22 Correct 4 ms 380 KB correct
23 Correct 4 ms 376 KB correct
24 Correct 4 ms 256 KB correct
25 Correct 2 ms 252 KB correct
26 Correct 4 ms 256 KB correct
27 Correct 4 ms 376 KB correct
28 Correct 3 ms 376 KB correct
29 Correct 3 ms 256 KB correct
30 Correct 4 ms 256 KB correct
31 Correct 4 ms 376 KB correct
32 Correct 4 ms 256 KB correct
33 Correct 4 ms 376 KB correct
34 Incorrect 240 ms 1132 KB WA in grader: NO
35 Halted 0 ms 0 KB -