Submission #1211257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211257		onbert	Simurgh (IOI17_simurgh)	C++17	13 / 100	672 ms	4440 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);
    }
}

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