oj.uz

Submission #1065613

# Submission time Handle Problem Language Result Execution time Memory
1065613 2024-08-19T10:00:03 Z mc061 Simurgh (IOI17_simurgh) C++17
51 / 100
 3000 ms 5744 KB 
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p;
    vector<int> sz;

    int get(int a) {
        return p[a] = (a == p[a] ? a : get(p[a]));
    }
    void merge(int a, int b) {
        int x = get(a);
        int y = get(b);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        p[x] = y;
        sz[y] += sz[x];
    }
    DSU(int n) {
        p.resize(n);
        sz.resize(n, 1);
        iota(p.begin(), p.end(), 0);
    }
};


const int N = 500;
vector<int> graph[N];
bool vis[N]={};
bool isBridge[N*N]={};
bool cant[N][N]={};
bool has_edge[N][N]={};
bool is_ans[N][N]={};
bool road_now[N][N]={};
int road_ind[N][N]={};
int cntv = 0;

int n;

int count_common_roads(const vector<int>& r);

void dfs(int v, int b1, int b2) {
    cntv++;
    vis[v] = true;
    for (int i = 0; i < graph[v].size(); ++i) {
        int u = graph[v][i];
        if (vis[u] || (u == b1 && v == b2) || (u == b2 && v == b1)) continue; 
        dfs(u, b1, b2);
    }
}

bool is_bridge(int v, int u) {
    cntv = 0;
    memset(vis, 0, sizeof(vis));
    dfs(0, v, u);
    assert(cntv <= n);
    return cntv != n;
}

void build(int v, vector<int>& comp) {
    vis[v] = true;
    comp.push_back(v);
    for (int u : graph[v]) if (!cant[v][u] && !vis[u]) build(u, comp);
}

vector<int> find_roads(int n_, vector<int> U, vector<int> V) {
    n = n_;
    vector<array<int, 3>> edges;

    for (int i = 0; i < U.size(); ++i) {
        int u = U[i], v = V[i];
        graph[v].push_back(u);
        graph[u].push_back(v);
        edges.push_back({u, v, i});
        has_edge[u][v] = has_edge[v][u] = true;
        road_ind[u][v] = road_ind[v][u] = i;
    }

    DSU tot(n);
    for (int i = 0; i < edges.size(); ++i) {
        int u = edges[i][0], v = edges[i][1];
        isBridge[i] = is_bridge(u, v);
        if (isBridge[i]) cant[u][v] = cant[v][u] = is_ans[v][u] = is_ans[u][v] = true, tot.merge(v, u);
    }

    memset(vis, 0, sizeof(vis));
    vector<vector<int>> comps;
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            comps.push_back({});
            build(i, comps[comps.size()-1]);
        }
    }

    vector<vector<int>> edges_from_v(n);


    for (vector<int> co : comps) {
        random_shuffle(co.begin(), co.end());
        memset(road_now, 0, sizeof(road_now));
        vector<pair<int, int>> edges_here;
        for (int i = 0; i < co.size(); ++i)
            edges_from_v[co[i]].clear();
        for (int i = 0; i < co.size(); ++i) {
            for (int j = i+1; j < co.size(); ++j) {
                if (!has_edge[co[i]][co[j]]) continue;
                edges_here.push_back({co[i], co[j]});
                edges_from_v[co[i]].push_back(co[j]);
                edges_from_v[co[j]].push_back(co[i]);
                road_now[co[i]][co[j]] = road_now[co[j]][co[i]] = true;
            }
        }
        random_shuffle(edges_here.begin(), edges_here.end());
        DSU d(n);
        vector<int> outside;
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                if (!road_now[i][j] && has_edge[i][j] && d.get(i) != d.get(j)) {
                    d.merge(i, j);
                    outside.push_back(road_ind[i][j]);
                }
            }
        }
        stack<int> st;
        st.push(co[0]);
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            vector<int> plus=outside;
            DSU d_here(n);
            for (int i = 0; i < edges_here.size(); ++i) {
                if (edges_here[i].first == v || edges_here[i].second == v) continue;
                if (d_here.get(edges_here[i].first) != d_here.get(edges_here[i].second)) {
                    d_here.merge(edges_here[i].first, edges_here[i].second);
                    plus.push_back(road_ind[edges_here[i].first][edges_here[i].second]);
                }
            }
            vector<pair<int, int>> res;
            bool included_bad = false;
            bool included_good = false;
            for (int i = 0; i < edges_from_v[v].size(); ++i) {
                int u = edges_from_v[v][i];
                if (!(tot.get(v) == tot.get(u) && included_bad)) {
                    if (tot.get(v) == tot.get(u)) {
                        if (is_ans[v][u] && !included_good) {
                            included_good = true;
                            // cerr << "purposefully including " << road_ind[v][u] << "\n";
                        }
                        else continue;
                    }
                    plus.push_back(road_ind[v][u]);
                    res.push_back({count_common_roads(plus), u});
                    plus.pop_back();
                }
            }
            sort(res.begin(), res.end());
            for (int i = 0; i < res.size(); ++i) {
                bool ok = res[i].first == res.back().first;
                if (!ok) continue;
                if (res[i].first == res.back().first && tot.get(res[i].second) != tot.get(v)) {
                    is_ans[res[i].second][v] = is_ans[v][res[i].second] = true;
                    tot.merge(v, res[i].second);
                    st.push(res[i].second);
                }
            }
        }
    }
    vector<int> res;
    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            if (is_ans[i][j]) res.push_back(road_ind[i][j]);
        }
    }
    // for (int i : res) cerr << i << " ";
    // cerr << "\n";
    sort(res.begin(), res.end());
    return res;
}

Compilation message

simurgh.cpp: In function 'void dfs(int, int, int)':
simurgh.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < graph[v].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = 0; i < U.size(); ++i) {
      |                     ~~^~~~~~~~~~
simurgh.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i = 0; i < edges.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~
simurgh.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int i = 0; i < co.size(); ++i)
      |                         ~~^~~~~~~~~~~
simurgh.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (int i = 0; i < co.size(); ++i) {
      |                         ~~^~~~~~~~~~~
simurgh.cpp:105:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             for (int j = i+1; j < co.size(); ++j) {
      |                               ~~^~~~~~~~~~~
simurgh.cpp:131:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |             for (int i = 0; i < edges_here.size(); ++i) {
      |                             ~~^~~~~~~~~~~~~~~~~~~
simurgh.cpp:141:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |             for (int i = 0; i < edges_from_v[v].size(); ++i) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~
simurgh.cpp:157:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |             for (int i = 0; i < res.size(); ++i) {
      |                             ~~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB correct
2 Correct 0 ms 604 KB correct
3 Correct 0 ms 604 KB correct
4 Correct 0 ms 600 KB correct
5 Correct 0 ms 604 KB correct
6 Correct 0 ms 604 KB correct
7 Correct 0 ms 604 KB correct
8 Correct 0 ms 604 KB correct
9 Correct 0 ms 720 KB correct
10 Correct 0 ms 604 KB correct
11 Correct 1 ms 716 KB correct
12 Correct 1 ms 604 KB correct
13 Correct 0 ms 604 KB correct
14 Correct 5 ms 860 KB correct
15 Correct 5 ms 860 KB correct
16 Correct 5 ms 924 KB correct
17 Correct 4 ms 860 KB correct
18 Correct 2 ms 860 KB correct
19 Correct 4 ms 856 KB correct
20 Correct 4 ms 860 KB correct
21 Correct 3 ms 856 KB correct
22 Correct 2 ms 860 KB correct
23 Correct 2 ms 860 KB correct
24 Correct 2 ms 860 KB correct
25 Correct 1 ms 860 KB correct
26 Correct 2 ms 856 KB correct
27 Correct 2 ms 860 KB correct
28 Correct 1 ms 860 KB correct
29 Correct 1 ms 860 KB correct
30 Correct 2 ms 860 KB correct
31 Correct 2 ms 860 KB correct
32 Correct 3 ms 892 KB correct
33 Correct 2 ms 860 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB correct
2 Correct 0 ms 604 KB correct
3 Correct 0 ms 604 KB correct
4 Correct 0 ms 600 KB correct
5 Correct 0 ms 604 KB correct
6 Correct 0 ms 604 KB correct
7 Correct 0 ms 604 KB correct
8 Correct 0 ms 604 KB correct
9 Correct 0 ms 720 KB correct
10 Correct 0 ms 604 KB correct
11 Correct 1 ms 716 KB correct
12 Correct 1 ms 604 KB correct
13 Correct 0 ms 604 KB correct
14 Correct 5 ms 860 KB correct
15 Correct 5 ms 860 KB correct
16 Correct 5 ms 924 KB correct
17 Correct 4 ms 860 KB correct
18 Correct 2 ms 860 KB correct
19 Correct 4 ms 856 KB correct
20 Correct 4 ms 860 KB correct
21 Correct 3 ms 856 KB correct
22 Correct 2 ms 860 KB correct
23 Correct 2 ms 860 KB correct
24 Correct 2 ms 860 KB correct
25 Correct 1 ms 860 KB correct
26 Correct 2 ms 856 KB correct
27 Correct 2 ms 860 KB correct
28 Correct 1 ms 860 KB correct
29 Correct 1 ms 860 KB correct
30 Correct 2 ms 860 KB correct
31 Correct 2 ms 860 KB correct
32 Correct 3 ms 892 KB correct
33 Correct 2 ms 860 KB correct
34 Correct 1885 ms 3120 KB correct
35 Correct 1718 ms 3092 KB correct
36 Correct 877 ms 2704 KB correct
37 Correct 11 ms 1368 KB correct
38 Correct 1857 ms 3124 KB correct
39 Correct 1387 ms 2956 KB correct
40 Correct 845 ms 2820 KB correct
41 Correct 1806 ms 3128 KB correct
42 Correct 1815 ms 3124 KB correct
43 Correct 558 ms 2384 KB correct
44 Correct 373 ms 2128 KB correct
45 Correct 508 ms 2132 KB correct
46 Correct 295 ms 2132 KB correct
47 Correct 72 ms 1620 KB correct
48 Correct 5 ms 1368 KB correct
49 Correct 12 ms 1368 KB correct
50 Correct 81 ms 1748 KB correct
51 Correct 499 ms 2128 KB correct
52 Correct 384 ms 2240 KB correct
53 Correct 311 ms 2136 KB correct
54 Correct 566 ms 2384 KB correct
55 Correct 518 ms 2388 KB correct
56 Correct 512 ms 2128 KB correct
57 Correct 526 ms 2132 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB correct
2 Correct 1 ms 604 KB correct
3 Execution timed out 3092 ms 5744 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB correct
2 Correct 0 ms 604 KB correct
3 Correct 0 ms 604 KB correct
4 Correct 0 ms 600 KB correct
5 Correct 0 ms 604 KB correct
6 Correct 0 ms 604 KB correct
7 Correct 0 ms 604 KB correct
8 Correct 0 ms 604 KB correct
9 Correct 0 ms 720 KB correct
10 Correct 0 ms 604 KB correct
11 Correct 1 ms 716 KB correct
12 Correct 1 ms 604 KB correct
13 Correct 0 ms 604 KB correct
14 Correct 5 ms 860 KB correct
15 Correct 5 ms 860 KB correct
16 Correct 5 ms 924 KB correct
17 Correct 4 ms 860 KB correct
18 Correct 2 ms 860 KB correct
19 Correct 4 ms 856 KB correct
20 Correct 4 ms 860 KB correct
21 Correct 3 ms 856 KB correct
22 Correct 2 ms 860 KB correct
23 Correct 2 ms 860 KB correct
24 Correct 2 ms 860 KB correct
25 Correct 1 ms 860 KB correct
26 Correct 2 ms 856 KB correct
27 Correct 2 ms 860 KB correct
28 Correct 1 ms 860 KB correct
29 Correct 1 ms 860 KB correct
30 Correct 2 ms 860 KB correct
31 Correct 2 ms 860 KB correct
32 Correct 3 ms 892 KB correct
33 Correct 2 ms 860 KB correct
34 Correct 1885 ms 3120 KB correct
35 Correct 1718 ms 3092 KB correct
36 Correct 877 ms 2704 KB correct
37 Correct 11 ms 1368 KB correct
38 Correct 1857 ms 3124 KB correct
39 Correct 1387 ms 2956 KB correct
40 Correct 845 ms 2820 KB correct
41 Correct 1806 ms 3128 KB correct
42 Correct 1815 ms 3124 KB correct
43 Correct 558 ms 2384 KB correct
44 Correct 373 ms 2128 KB correct
45 Correct 508 ms 2132 KB correct
46 Correct 295 ms 2132 KB correct
47 Correct 72 ms 1620 KB correct
48 Correct 5 ms 1368 KB correct
49 Correct 12 ms 1368 KB correct
50 Correct 81 ms 1748 KB correct
51 Correct 499 ms 2128 KB correct
52 Correct 384 ms 2240 KB correct
53 Correct 311 ms 2136 KB correct
54 Correct 566 ms 2384 KB correct
55 Correct 518 ms 2388 KB correct
56 Correct 512 ms 2128 KB correct
57 Correct 526 ms 2132 KB correct
58 Correct 0 ms 600 KB correct
59 Correct 1 ms 604 KB correct
60 Execution timed out 3092 ms 5744 KB Time limit exceeded
61 Halted 0 ms 0 KB -