Submission #1211254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211254		onbert	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	320 KiB

simurgh

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

const int maxn = 505, INF = 1e5;
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;
    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);
    }
    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]) {
        edge(u, v, 1);
        dfs0(v);
    }
}

void dfs1(int u) {
    vis[u] = true;
    for (int v:adj[u]) if (!vis[v]) {
        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 = (int)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) {
    assert(false);
    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);
        nodes.clear();
        for (int i=0;i<n;i++) if (state[i] <= 0) {
            dfs0(i);
            break;
        }
        connect();

        pair<int, pair<int,int>> mx;
        for (int u:nodes) {
            // state[u] = 0;
            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);
                int val = qry();
                mx = max(make_pair(val, make_pair(V, u)), mx);
                edge(u, V, 0);
            }
        }
        for (int u:nodes) {
            // state[u] = 0;
            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);
                int val = qry();
                assert(val == mx.first || val + 1 == mx.first);
                edge(u, V, 0);
            }
        }
        int v = mx.second.first, u = mx.second.second;
        gold[min(u, v)][max(u, v)] = 1;
        state[u] = 2;
        fa[u] = v;
        goldcnt++;
        // 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: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30