Submission #1219583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219583		JooDdae	Simurgh (IOI17_simurgh)	C++20	100 / 100	179 ms	6152 KiB

simurgh

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

#define getMin(id) min(in[a[id]], in[b[id]])

int N, M, D, a[250250], b[250250], pe[505], mn[505], mx[505], g[250250], in[505], ch[505], t[250250], cnt;
vector<int> v[505];

int p[250250];
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }

void dfs(int u, int p) {
    in[u] = ++cnt;
    for(auto id : v[u]) {
        int x = a[id] ^ b[id] ^ u;
        if(x == p) continue;

        if(!in[x]) {
            pe[x] = mn[x] = ch[u] = id, t[id] = 1;
            dfs(x, u);
            if(u && getMin(mn[x]) <= getMin(mn[u])) mn[u] = mn[x], mx[u] = mx[x];
        } else if(in[x] <= getMin(mn[u])) mn[u] = id, mx[u] = ch[x];
    }
}

int query(const set<int> &S) {
    return count_common_roads(vector<int>(S.begin(), S.end()));
}

int query(set<int> S, vector<int> L) {
    int p = 0;
    for(auto id : L) {
        int x = pe[in[a[id]] > in[b[id]] ? a[id] : b[id]];
        p += g[x], S.erase(x), S.insert(id);
    }
    return query(S) - (D-p);
}

void solve(int l, int r, int s, const set<int> &S, const vector<int> &L) {
    if(!s) return;
    if(l == r) {
        g[L[l]] = 1;
        return;
    }

    int mid = (l+r) >> 1;
    int ls = query(S, vector<int>(L.begin()+l, L.begin()+mid+1));

    solve(l, mid, ls, S, L);
    solve(mid+1, r, s-ls, S, L);
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
    ::N = N, M = U.size();
    for(int i=0;i<M;i++) {
        a[i] = U[i], b[i] = V[i];
        v[a[i]].push_back(i);
        v[b[i]].push_back(i);
    }
    dfs(0, -1);

    set<int> S;
    for(int i=1;i<N;i++) S.insert(pe[i]);
    D = query(S);
    if(D == N-1) return vector<int>(S.begin(), S.end());
    
    iota(p, p+M, 0), memset(g, -1, sizeof g);
    for(int i=1;i<N;i++) {
        if(pe[i] == mn[i]) {
            g[pe[i]] = 1;
            continue;
        }
        
        S.erase(pe[i]), S.insert(mn[i]);
        int d = query(S);
        if(d > D) g[pe[i]] = 0, g[mn[i]] = 1;
        if(d < D) g[pe[i]] = 1, g[mn[i]] = 0;
        if(d == D) p[find(pe[i])] = find(mn[i]);

        S.insert(pe[i]), S.erase(mx[i]);
        d = query(S);
        if(d > D) g[mx[i]] = 0, g[mn[i]] = 1;
        if(d < D) g[mx[i]] = 1, g[mn[i]] = 0;
        if(d == D) p[find(mx[i])] = find(mn[i]);

        S.insert(mx[i]), S.erase(mn[i]);
    }
    
    for(int i=0;i<M;i++) if(g[i] != -1) g[find(i)] = g[i];
    for(int i=0;i<M;i++) g[i] = g[find(i)];
    for(int i=0;i<M;i++) if(g[i] == -1) g[i] = 0;

    for(int i=0;i<N;i++) {
        vector<int> L;
        for(auto x : v[i]) if(!g[x] && in[i] < in[a[x]^b[x]^i]) L.push_back(x);
        if(!L.empty()) solve(0, L.size()-1, query(S, L), S, L);
    }

    vector<int> re;
    for(int i=0;i<M;i++) if(g[i]) re.push_back(i);
    return re;
}

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