Submission #1065613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065613		mc061	Simurgh (IOI17_simurgh)	C++17	51 / 100	3092 ms	5744 KiB

simurgh

#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 (stderr)

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 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30