Submission #372237

#	Time	Username	Problem	Language	Result	Execution time	Memory
372237		doowey	Simurgh (IOI17_simurgh)	C++14	0 / 100	4 ms	3308 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = 500;
const int M = N * (N - 1) / 2;
vector<pii> T[N];
bool bridge[M];
bool tree[M];
int dep[N];
pii low[N];
int in[N];

vector<int> nom;

void dfs(int u, int par){
    low[u] = mp(dep[u],-1);
    for(auto x : T[u]){
        if(x.fi == par) continue;
        if(dep[x.fi] == -1){
            dep[x.fi] = dep[u] + 1;
            in[x.fi] = x.se;
            nom.push_back(x.se);
            dfs(x.fi, u);
            low[u] = min(low[u], low[x.fi]);
            if(dep[u] < low[x.fi].fi){
                bridge[x.se] = true;
            }
            tree[x.se] = true;
        }
        else{
            low[u] = min(low[u], mp(dep[x.fi], x.se));
        }
    }
}

int can[M];
bool vis[M];
vector<int> G[M];

int get(int i, int j){ // delete i and add j
    vector<int> nw;
    for(auto x : nom) if(x != i) nw.push_back(x);
    nw.push_back(j);
    return count_common_roads(nw);
}

vector<int> cyc;

void dfs1(int u){
    cyc.push_back(u);
    vis[u]=true;
    for(auto x : G[u]){
        if(!vis[x]) dfs1(x);
    }
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    for(int i = 0 ; i < n; i ++ ){
        dep[i] = -1;
    }
    int m = u.size();
    for(int i = 0 ; i < m; i ++ ){
        T[u[i]].push_back(mp(v[i], i));
        T[v[i]].push_back(mp(u[i], i));
        can[i] = -1;
    }
    for(int i = 0 ; i < m; i ++ ){
        if(dep[u[i]] > dep[v[i]]) swap(u[i], v[i]);
    }
    dep[0] = 0;
    dfs(0, -1);
    int def = count_common_roads(nom);
    int exc;
    int ui, vi;
    for(int i = 0 ; i < m; i ++ ){
        if(bridge[i]) {
            can[i] = 1;
            continue;
        }
        else{
            if(tree[i]){
                ui = i;
                vi = low[v[i]].se;
            }
            else{
                ui = in[v[i]];
                vi = i;
            }
            exc = get(ui, vi);
            if(exc == def){
                G[ui].push_back(vi);
                G[vi].push_back(ui);
            }
            else{
                if(exc == def + 1){
                    can[ui] = 0;
                    can[vi] = 1;
                }
                else{
                    can[ui] = 1;
                    can[vi] = 0;
                }
            }
        }
    }
    int val;
    for(int i = 0 ; i < m ; i ++ ){
        if(vis[i]) continue;
        cyc.clear();
        dfs1(i);
        val = -1;
        for(auto x : cyc){
            if(can[x] != -1)
                val = can[x];
        }
        if(val == -1) val = 0;
        for(auto x : cyc)
            can[x] = val;
    }
    vector<int> outp;
    for(int i = 0 ; i < m ; i ++ ){
        if(can[i])outp.push_back(i);
    }
	return outp;
}

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