Submission #69805

#	Time	Username	Problem	Language	Result	Execution time	Memory
69805		aquablitz11	Simurgh (IOI17_simurgh)	C++14	51 / 100	1382 ms	5164 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
 
using pii = pair<int, int>;
const int N = 510;
const int M = N*(N-1)/2;
const int LIM = 30000;
 
vector<pii> G[N];
vector<int> E;
 
int par[N];
int root(int u) {
    if (par[u] == u) return u;
    return par[u] = root(par[u]);
}
bool merge(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) return false;
    par[u] = v;
    return true;
}
 
bool tree[M];
int ans[M];
 
vector<int> find_roads(int n, vector<int> U, vector<int> V)
{
    int cntq = 0;
 
    int m = U.size();
    iota(par, par+n, 0);
    fill(ans, ans+m, -1);
    for (int i = 0; i < m; ++i) {
        int u = U[i], v = V[i];
        if (merge(u, v)) {
            G[u].emplace_back(v, i);
            G[v].emplace_back(u, i);
            E.push_back(i);
            tree[i] = true;
        }
    }
    if (++cntq == LIM) assert(false);
    int defcnt = count_common_roads(E);
    for (int i = 0; i < m; ++i) if (!tree[i]) {
        int u = U[i], v = V[i];
        vector<int> par(n, -1);
        vector<int> ix(n, -1);
        par[u] = u;
        queue<int> Q;
        Q.push(u);
        while (!Q.empty()) {
            int s = Q.front(); Q.pop();
            if (s == v) break;
            for (auto t : G[s]) if (par[t.first] == -1) {
                par[t.first] = s;
                ix[t.first] = t.second;
                Q.push(t.first);
            }
        }
        map<int, bool> inp;
        vector<int> path;
        int s = v;
        do {
            inp[ix[s]] = true;
            path.push_back(ix[s]);
            s = par[s];
        } while (s != u);
 
        int typ = -1; // not -1 = found determined
        for (auto e : path) {
            if (ans[e] != -1) {
                typ = e;
                break;
            }
        }
        vector<int> other;
        for (auto e : E) {
            if (!inp[e])
                other.push_back(e);
        }
        if (typ == -1) {
            ans[i] = 0;
            for (auto e : path) {
                vector<int> q(other.begin(), other.end());
                for (auto p : path) if (p != e)
                    q.push_back(p);
                q.push_back(i);
                if (++cntq == LIM) assert(false);
                int cnt = count_common_roads(q);
                if (cnt-defcnt == 1)
                    ans[e] = 0, ans[i] = 1;
                else if (cnt-defcnt == -1)
                    ans[i] = 0, ans[e] = 1;
            }
            if (ans[i] == -1) ans[i] = 0;
            for (auto e : path) if (ans[e] == -1)
                ans[e] = ans[i];
        } else {
            vector<int> q(other.begin(), other.end());
            for (auto e : path) if (e != typ)
                q.push_back(e);
            q.push_back(i);
            if (++cntq == LIM) assert(false);
            int cnt = count_common_roads(q);
            ans[i] = ans[typ]+(cnt-defcnt);
            for (auto e : path) if (ans[e] == -1) {
                q = vector<int>(other.begin(), other.end());
                for (auto p : path) if (p != e) q.push_back(p);
                q.push_back(i);
                if (++cntq == LIM) assert(false);
                int cnt = count_common_roads(q);
                if (cnt-defcnt == 1) ans[e] = 0;
                else if (cnt-defcnt == -1) ans[e] = 1;
                else ans[e] = ans[i];
            }
        }
    }
    vector<int> ret;
    ret.reserve(n-1);
    for (int i = 0; i < m; ++i) {
        if (ans[i] != 0)
            ret.push_back(i);
    }
    return ret;
}

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