oj.uz

Submission #1067269

# Submission time Handle Problem Language Result Execution time Memory
1067269 2024-08-20T13:46:32 Z Ignut Simurgh (IOI17_simurgh) C++17
30 / 100
 154 ms 3260 KB 
// Ignut

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct DSU {
    vector<int> p, sz;
    void Init(int n) {
        p.assign(n, 0);
        iota(p.begin(), p.end(), 0);
        sz.assign(n, 1);
    }
    int Get(int v) {
        return p[v] == v ? v : p[v] = Get(p[v]);
    }
    bool Unite(int u, int v) {
        u = Get(u), v = Get(v);
        if (u == v) return false;
        if (sz[u] > sz[v]) swap(u, v);
        sz[v] += sz[u];
        p[u] = v;
        return true;
    }
};

const int N = 555;

vector<int> g[N];

bool ans[N * N];

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    int m = u.size();
    for (int i = 0; i < m; i ++) {
        g[u[i]].push_back(i);
        g[v[i]].push_back(i);
    }
    DSU dsu;
    dsu.Init(n);
    vector<int> have;
    for (int i = 0; i < m; i ++) {
        if (dsu.Unite(u[i], v[i])) {
            have.push_back(i);
        }
    }

    int cnt = count_common_roads(have);
    while (cnt < n - 1) {
        vector<int> next_have;
        int del_val = -1;
        for (int i : have) {
            if (ans[i]) continue;
            for (int j : have) if (j != i) next_have.push_back(j);
            del_val = i;
            break;
        }
        map<int, int> mp;
        for (int i : next_have) mp[i] ++;
        DSU dsu2; dsu2.Init(n);
        for (int i : next_have) dsu2.Unite(u[i], v[i]);
        bool got = false;
        for (int i = 0; i < m; i ++) {
            if (mp.count(i)) continue;
            DSU dsu3 = dsu2;
            if (!dsu3.Unite(u[i], v[i])) continue;

            next_have.push_back(i);
            int c = count_common_roads(next_have);
            if (c > cnt) {
                got = true;
                ans[i] = true;
                have = next_have;
                break;
            }
            next_have.pop_back();
        }
        if (!got) {
            ans[del_val] = true;
        }
        cnt = count_common_roads(have);
    }
    return have;   
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 1 ms 348 KB correct
5 Correct 1 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 344 KB correct
9 Correct 1 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 0 ms 348 KB correct
13 Correct 0 ms 348 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 0 ms 348 KB correct
4 Correct 1 ms 348 KB correct
5 Correct 1 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 0 ms 348 KB correct
8 Correct 0 ms 344 KB correct
9 Correct 1 ms 348 KB correct
10 Correct 0 ms 348 KB correct
11 Correct 0 ms 348 KB correct
12 Correct 0 ms 348 KB correct
13 Correct 0 ms 348 KB correct
14 Correct 4 ms 344 KB correct
15 Correct 3 ms 348 KB correct
16 Correct 3 ms 348 KB correct
17 Correct 4 ms 348 KB correct
18 Correct 2 ms 348 KB correct
19 Correct 5 ms 500 KB correct
20 Correct 4 ms 348 KB correct
21 Correct 3 ms 348 KB correct
22 Correct 0 ms 348 KB correct
23 Correct 0 ms 348 KB correct
24 Correct 1 ms 348 KB correct
25 Correct 0 ms 348 KB correct
26 Correct 0 ms 464 KB correct
27 Correct 1 ms 348 KB correct
28 Correct 0 ms 348 KB correct
29 Correct 0 ms 456 KB correct
30 Correct 1 ms 348 KB correct
31 Correct 0 ms 348 KB correct
32 Correct 1 ms 348 KB correct
33 Correct 1 ms 348 KB correct

Subtask #3
0 / 21.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB correct
2 Correct 0 ms 348 KB correct
3 Incorrect 154 ms 3260 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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