Submission #720398

#	Time	Username	Problem	Language	Result	Execution time	Memory
720398		Jarif_Rahman	Simurgh (IOI17_simurgh)	C++17	51 / 100	125 ms	4684 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, m;
vector<vector<pair<int, int>>> graph, tree, backedge;
vector<bool> bl;
vector<bool> royal;
vector<int> depth;
vector<int> cur;
vector<pair<int, int>> DD;
int X;

void dfs0(int nd, int d = 0, int pi = -1){
    bl[nd] = 1;
    depth[nd] = d;
    for(auto [x, i]: graph[nd]) if(i != pi) {
        if(bl[x]){
            if(depth[x] < depth[nd]) backedge[nd].pb({x, i});
        }
        else{
            bl[x] = 1;
            tree[nd].pb({x, i});
            cur.pb(i);
            dfs0(x, d+1, i);
        }
    }
}


int ND;
pair<int, int> D;
void dfs_find(int nd, int ss = -1){
    if(DD[nd].f != -1 && depth[DD[nd].f] < depth[D.f]) D = DD[nd];
    if(depth[nd] < depth[ND]) return;
    for(auto [x, i]: graph[nd]) if(royal[i] && x != ss) dfs_find(x, nd);
}

void dfs(int nd, int i){
    for(auto [x, j]: tree[nd]) dfs(x, j);
    if(i == -1) return;
    ND = nd;
    D = {nd, i};
    dfs_find(nd);

    auto it = find(cur.begin(), cur.end(), i);
    if(depth[nd] <= depth[D.f]){
        vector<int> ge, eq = {i};
        pair<int, int> eq_mn = D, ge_mn = D;
        for(auto [x, j]: backedge[nd]){
            *it = j;
            int c = count_common_roads(cur);
            if(c == X){
                eq.pb(j);
                if(depth[x] < depth[eq_mn.f]) eq_mn = {x, j};
            }
            else if(c > X){
                ge.pb(j);
                if(depth[x] < depth[ge_mn.f]) ge_mn = {x, j};
            }
        }
        *it = i;
        if(ge.empty()) for(int j: eq) royal[j] = 1;
        else for(int j: ge) royal[j] = 1;
        if(ge.empty()) DD[nd] = eq_mn;
        else DD[nd] = ge_mn;
    }
    else{
        *it = D.sc;
        int Y = count_common_roads(cur);
        for(auto [x, j]: backedge[nd]){
            *it = j;
            int c = count_common_roads(cur);
            if(c == Y){
                royal[j] = 1;
                if(depth[x] < depth[D.f]) D = {x, j};
            }
        }
        *it = i;
        if(X == Y) royal[i] = 1;
        DD[nd] = D;
    }
}

vector<int> find_roads(int _n, vector<int> U, vector<int> V){
    swap(n, _n);
    m = U.size();
    graph.resize(n);
    tree.resize(n);
    backedge.resize(n);
    bl.assign(n, 0);
    depth.resize(n);
    royal.assign(m, 0);
    DD.resize(n, {-1, -1});

    for(int i = 0; i < m; i++){
        graph[U[i]].pb({V[i], i});
        graph[V[i]].pb({U[i], i});
    }
    dfs0(0);
    X = count_common_roads(cur);
    dfs(0, -1);
    vector<int> ans;
    for(int i = 0; i < m; i++) if(royal[i]) ans.pb(i);
    return ans;
}

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