Submission #1219574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219574		JooDdae	Simurgh (IOI17_simurgh)	C++20	51 / 100	116 ms	4472 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, 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()));
}

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]);
    int 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;
        }
        // cout << i << " " << pe[i] << " " << mn[i] << " " << mx[i] << "\n";
 
        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++) cout << g[i] << " \n"[i == M-1];

    for(int i=0;i<M;i++) if(g[i] != -1) g[find(i)] = g[i];
    // for(int i=0;i<M;i++) cout << g[i] << " \n"[i == M-1];

    for(int i=0;i<M;i++) g[i] = g[find(i)];
    // for(int i=0;i<M;i++) cout << g[i] << " \n"[i == M-1];
    // for(int i=1;i<N;i++) cout << i << "/" << g[pe[i]] << " \n"[i == N-1];

    for(int i=0;i<M;i++) if(g[i] == -1) g[i] = 0;

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

    for(int i=0;i<M;i++) if(!t[i] && !g[i]) {
        int x = in[a[i]] > in[b[i]] ? a[i] : b[i];
        S.erase(pe[x]), S.insert(i);
        if(D-g[pe[x]] < query(S)) re.push_back(i);
        S.insert(pe[x]), S.erase(i);
    }

    return re;
}

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