Submission #237382

#	Time	Username	Problem	Language	Result	Execution time	Memory
237382		lyc	Simurgh (IOI17_simurgh)	C++14	100 / 100	668 ms	13808 KiB

simurgh

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

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
using vi = vector<int>;

const int mxN = 505;
const int mxM = (500*499)/2 + 10;
const int mxQ = 8000;
int N, M, q = 0;
int U[mxM], V[mxM];
vector<int> al[mxN];
vector<int> span;
int golden[mxM];

struct UnionFind {
    vector<int> pa, sz; int comp;
    UnionFind(int n) { pa.assign(n,0); iota(ALL(pa),0); sz.assign(n,0); comp = n;}
    int findset(int i) { return (i == pa[i]) ? i : (pa[i] = findset(pa[i])); }
    bool unionset(int i, int j) {
        int x = findset(i), y = findset(j);
        if (x != y) {
            --comp;
            if (sz[x] < sz[y]) swap(x,y);
            sz[x] += sz[y], pa[y] = x;
            return true;
        } return false;
    }
};

int ask(vector<int> edges, bool sub=false) {
    //assert(++q <= mxQ);
    UnionFind UF(N);
    for (int e : edges) {
        int u = U[e], v = V[e];
        assert(UF.unionset(u,v));
        UF.unionset(u,v);
    }
    int cnt = 0;
    for (int e : span) if (UF.unionset(U[e],V[e])) {
        edges.push_back(e);
        cnt += (golden[e] == 1);
    }
    //cout << "ASK: "; for (int e : edges) { cout << U[e] _ V[e] << ", "; } cout << endl;
    assert(UF.comp == 1);
    return count_common_roads(edges) - (sub ? cnt : 0);
}

int pa[mxN], pre[mxN], low[mxN], dfc, dfr;
vi ears[mxM];
int esz = 0;
vi* cur[mxN];
vector<vi*> decomp;
void dfs(int u, int p) {
    pre[u] = low[u] = dfc++;
    vector<vi*> vec;
    for (int e : al[u]) {
        int v = U[e]^V[e]^u;
        if (v == p) continue;
        if (pre[v] == -1) {
            pa[v] = e;
            dfs(v,u);
            span.push_back(e);
            if (low[v] > pre[u]) { // bridge
                golden[e] = 1;
                if (cur[v] != nullptr) decomp.push_back(cur[v]);
            } else {
                low[u] = min(low[u],low[v]);
                cur[v]->push_back(e);
                vec.push_back(cur[v]);
            }
        } else if (pre[v] < pre[u]) {
            low[u] = min(low[u],pre[v]);
            ears[esz] = {v,e};
            vec.push_back(&ears[esz++]);
        }
    }
    int fst = 0;
    cur[u] = nullptr;
    for (vi* x : vec) {
        int d = pre[*x->begin()];
        if (d > low[u] || (d == low[u] && ++fst > 1)) decomp.push_back(x);
        else cur[u] = x;
    }
    if (u == dfr && cur[u] != nullptr) decomp.push_back(cur[u]);
}

void solve(vi* ear) {
    //{cout << "EAR " << SZ(*ear) << ": ";
    //int u = *ear->begin();
    //bool fst = 1;
    //for (int e : (*ear)) {
    //    if (fst) fst = 0;
    //    else u ^= U[e]^V[e];
    //    cout << u << ' ';
    //}
    //cout << endl;}

    vector<int> x[2];
    int u = (*ear)[0], v = u, f = (*ear)[1];
    FOR(i,1,SZ(*ear)-1){
        int e = (*ear)[i];
        if (i > 1) x[golden[e] != -1].push_back(e);
        v ^= U[e]^V[e];
    }
    while (v != u) {
        x[golden[pa[v]] != -1].push_back(pa[v]);
        v ^= U[pa[v]]^V[pa[v]];
    }
    if (x[0].empty());
    else if (x[1].empty()) {
        vector<int> que;
        //cout << f << " CASE 1: ";
        //for (int& e : x[0]) cout << e << ": " << U[e] _ V[e] << ", ";
        //cout << endl;
        int mx = ask(x[0]);
        FOR(i,0,SZ(x[0])-1){
            //TRACE("ask" _ x[0][i] _ "without" _ U[x[0][i]] _ V[x[0][i]]);
            swap(x[0][i],f);
            int q = ask(x[0]);
            swap(x[0][i],f);
            que.push_back(q);
            mx = max(mx,q);
        }
        FOR(i,0,SZ(x[0])-1){
            //TRACE(i _ que[i] _ mx);
            golden[x[0][i]] = que[i] < mx; // removed decreases
        }
    } else {
        vector<int> edges(x[0]);
        FOR(i,1,SZ(x[1])-1) edges.push_back(x[1][i]);
        edges.push_back(f);
        //cout << f << " CASE 2: ";
        //for (int& e : x[0]) cout << e << ": " << U[e] _ V[e] << ", ";
        //cout << endl;
        int r = ask(edges);
        FOR(i,0,SZ(x[0])-1){
            swap(edges[i],x[1][0]);
            int q = ask(edges);
            swap(edges[i],x[1][0]);
            golden[x[0][i]] = ((golden[x[1][0]] && q == r) || q < r);
        }
    }
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    N = n;
    M = SZ(u);
    FOR(i,0,M-1){
        U[i] = u[i], V[i] = v[i];
        al[u[i]].push_back(i);
        al[v[i]].push_back(i);
    }

    fill(golden,golden+M,-1);
    fill(pre,pre+n,-1); dfc = dfr = 0;
    dfs(0,-1);

    for (vi* x : decomp) solve(x);
    //for (int& e : span) { TRACE(e _ ":" _ U[e] _ V[e] _ golden[e]); }

    FOR(i,0,N-1) {
        for (;;) {
            vector<int> all;
            for (int e : al[i]) if (golden[e] == -1) all.push_back(e);
            if (all.empty()) break;
            if (!ask(all,true)) {
                for (int e : all) golden[e] = 0;
                break;
            }
            int lo = -1, hi = SZ(all)-1;
            while (hi-lo > 1) {
                int mid = (lo+hi)/2;
                vector<int> edges;
                FOR(i,lo+1,mid) edges.push_back(all[i]);
                if (ask(edges,true)) hi = mid;
                else lo = mid;
            }
            golden[all[hi]] = 1;
        }
    }

    vector<int> ans;
    FOR(i,0,M-1) if (golden[i] == 1) ans.push_back(i);
	return ans;
}

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