Submission #1211207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211207		onbert	Simurgh (IOI17_simurgh)	C++17	32 / 100	842 ms	6336 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 505;
int n;
int id[maxn][maxn];
vector<int> adj[maxn];
bool a[maxn][maxn];
int gold[maxn][maxn], state[maxn];
int fa[maxn];
int goldcnt;

void edge(int u, int v, bool x) {
    a[min(u, v)][max(u, v)] = x;
}

int qry() {
    vector<int> ask;
    int ret = 0;
    int edges = 0;
    for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) if (a[i][j]) {
        ask.push_back(id[i][j]);
        ret -= (gold[i][j] == 1);
        edges++;
    }
    assert(edges == n-1);
    return ret + count_common_roads(ask);
}

vector<int> nodes;
bool vis[maxn];
void dfs0(int u) {
    vis[u] = true, nodes.push_back(u);
    for (int v:adj[u]) if (!vis[v] && state[v] <= 0) {
        edge(u, v, 1);
        dfs0(v);
    }
}

void dfs1(int u) {
    vis[u] = true;
    for (int v:adj[u]) if (!vis[v] && state[v] <= 0) {
        edge(u, v, 1);
        dfs1(v);
    }
}

void connect() {
    for (int i=0;i<n;i++) if (state[i] == 2) dfs1(i);
}

void dfs2(int u) {
    vis[u] = true;
    for (int v:adj[u]) if (!vis[v] && !(state[v] == 0 && state[u] != 2)) {
        edge(u, v, 1);
        fa[v] = u;
        dfs2(v);
    }
}

void addnode(int u, int FA) {
    goldcnt++;
    for (int i=0;i<n;i++) vis[i] = (state[i] == 2);
    for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j] = (gold[i][j] == 1 && state[i] == 2 && state[j] == 2);
    for (int i=0;i<n;i++) if (state[i] == 2 && i != u) {
        dfs2(i);
    }
    vector<int> cand;
    for (int v:adj[u]) if (state[v] == 0) cand.push_back(v);
    // cout << u << endl;
    // for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j]) cout << i << " " << j << endl;
    int init = qry();
    // cout << init << endl;
    for (int v:cand) {
        edge(u, v, 1);
        edge(v, fa[v], 0);
    }
    int val = qry();
    // cout << endl;
    // for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j]) cout << i << " " << j << endl;
    // cout << val << endl;
    for (int v:cand) {
        edge(u, v, 0);
        edge(v, fa[v], 1);
    }
    vector<int> add;
    for (int i=init + 1;i<=val;i++) {
        int l = 0, r = cand.size()-1;
        while (l < r) {
            int mid = (l+r)/2;
            for (int j=0;j<=mid;j++) {
                int v = cand[j];
                edge(u, v, 1);
                edge(v, fa[v], 0);
            }
            int val = qry();
            for (int j=0;j<=mid;j++) {
                int v = cand[j];
                edge(u, v, 0);
                edge(v, fa[v], 1);
            }
            if (val >= init+1) r = mid;
            else l = mid+1;
        }
        int v = cand[l];
        add.push_back(v);
        gold[min(u, v)][max(u, v)] = 1;
        // cout << "addnode " << u << " " << v << endl;
    }
    state[u] = 2;
    fa[u] = FA;
    for (int v:add) addnode(v, u);
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
    n = N;
	for (int i=0;i<n;i++) for (int j=0;j<n;j++) id[i][j] = -1, a[i][j] = 0, gold[i][j] = -1;
    for (int i=0;i<U.size();i++) {
        id[min(U[i], V[i])][max(U[i], V[i])] = i;
        adj[U[i]].push_back(V[i]); adj[V[i]].push_back(U[i]);
    }
    for (int i=0;i<n;i++) state[i] = -1, fa[i] = -1;
    state[0] = 2;
    goldcnt = 1;

    while (goldcnt < n) {
        // cout << "start " << goldcnt << endl;
        for (int i=0;i<n;i++) vis[i] = (state[i] == 2);
        for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j] = (gold[i][j] == 1);
        for (int i=0;i<n;i++) if (state[i] == -1) {
            nodes.clear();
            dfs0(i);
            break;
        }
        // cout << "edges\n";
        // for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (a[i][j]) cout << i << " " << j << endl;
        // cout << "nodes\n";
        // for (int i:nodes) cout << i << " "; cout << endl;
        connect();
        vector<pair<int,int>> vec;
        int mx = 0;
        for (int u:nodes) if (state[u] == -1) {
            vector<int> cand;
            for (int v:adj[u]) if (state[v] == 2) cand.push_back(v);
            if (!cand.size()) continue;
            sort(cand.begin(), cand.end());
            for (int v:cand) {
                edge(u, v, 1);
                if (v != cand[0]) edge(v, fa[v], 0);
            }
            int val = qry();
            vec.push_back({u, val});
            mx = max(val, mx);
            for (int v:cand) {
                edge(u, v, 0);
                if (v != cand[0]) edge(v, fa[v], 1);
            }
        }

        vector<pair<int,int>> add;
        for (auto [u, val]:vec) {
            state[u] = 0;
            vector<int> cand;
            for (int v:adj[u]) if (state[v] == 2) cand.push_back(v);
            sort(cand.begin(), cand.end());
            if (val == mx) {
                int l = 0, r = cand.size() - 1;
                while (l < r) {
                    int mid = (l+r)/2;

                    for (int i=0;i<=mid;i++) {
                        int v = cand[i];
                        edge(u, v, 1);
                        if (v != cand[0]) edge(v, fa[v], 0);
                    }
                    int val = qry();
                    for (int i=0;i<=mid;i++) {
                        int v = cand[i];
                        edge(u, v, 0);
                        if (v != cand[0]) edge(v, fa[v], 1);
                    }

                    if (val == mx) r = mid;
                    else l = mid+1;
                }
                int v = cand[l];
                add.push_back({u, v});
                gold[min(u, v)][max(u, v)] = 1;
                // cout << "oriadd " << u << " " << v << endl;
                // for (int j:cand) cout << j << " "; cout << endl;
            }
        }
        for (auto [u, v]:add) {
            addnode(u, v);
        }
        // cout << "test " << goldcnt << endl;;
        // cout << goldcnt << endl;
    }
    vector<int> ans;
    for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (gold[i][j] == 1) {
        ans.push_back(id[i][j]);
    }
    return ans;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30