Submission #372282

#	Time	Username	Problem	Language	Result	Execution time	Memory
372282		doowey	Simurgh (IOI17_simurgh)	C++14	51 / 100	161 ms	7404 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];
int dep[N];
pii low[N];
int in[N];

int edge[M];
int know[M];
vector<int> fq;

void dfs(int u, int pp){
    low[u] = mp(dep[u], -1);
    for(auto x : T[u]){
        if(x.fi == pp) continue;
        if(dep[x.fi] == -1){
            in[x.fi]=x.se;
            dep[x.fi]=dep[u]+1;
            dfs(x.fi, u);
            fq.push_back(x.se);
            low[u] = min(low[u], low[x.fi]);
            if(dep[u] < low[x.fi].fi){
                know[x.se] = 1;
                edge[x.se] = -1; // bridge
            }
            else{
                edge[x.se] = 0; //
            }
        }
        else{
            edge[x.se] = 2; // these f*ck everything up
            low[u] = min(low[u], mp(dep[x.fi], x.se));
        }
    }
}

vector<int> G[M];

int get(int ii, int jj){
    vector<int> aq;
    for(auto x : fq) if(x != ii) aq.push_back(x);
    aq.push_back(jj);
    return count_common_roads(aq);
}

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

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
    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));
        edge[i] = -1;
        know[i]=-1;
    }
    for(int i = 0 ; i < n; i ++ ){
        dep[i] = -1;
    }
    dep[0]=0;
    dfs(0,-1);
    for(int i = 0 ; i < m ; i ++) {
        if(dep[u[i]] > dep[v[i]])
            swap(u[i], v[i]);
    }
    for(int i = 1; i < n; i ++ ){
        edge[low[i].se] = 1;
    }
    int faf = count_common_roads(fq);
    int nw;
    int uu, vv;
    int go;
    for(int i = 0 ; i < m ; i ++ ){
        if(edge[i] == 0){
            uu = i;
            vv = low[v[i]].se;
            nw = get(uu, vv);
            if(faf == nw){
                G[uu].push_back(vv);
                G[vv].push_back(uu);
            }
            else{
                if(nw > faf){
                    know[vv]=1;
                    know[uu]=0;
                }
                else{
                    know[vv]=0;
                    know[uu]=1;
                }
            }
        }
        else if(edge[i] == 1){
            vv = i;
            go = v[i];
            while(u[in[go]] != u[i]){
                go = u[in[go]];
            }
            uu = in[go];
            nw = get(uu, vv);
            if(faf == nw){
                G[uu].push_back(vv);
                G[vv].push_back(uu);
            }
            else{
                if(nw > faf){
                    know[vv]=1;
                    know[uu]=0;
                }
                else{
                    know[vv]=0;
                    know[uu]=1;
                }
            }
        }
    }
    int val;
    for(int i = 0 ; i < m ; i ++ ){
        if(edge[i] == 0 || edge[i] == 1){
            if(!vis[i]){
                cyc.clear();
                dfs1(i);
                val = -1;
                for(auto x : cyc){
                    if(know[x] != -1) val = know[x];
                }
                if(val == -1) val = 0;
                for(auto x : cyc) know[x] = val;
            }
        }
    }
    vector<int> soln;
    for(int i = 0 ; i < m ; i ++ ){
        if(edge[i] == 2){
           nw = get(in[v[i]],i);
           know[i]=know[in[v[i]]]+(nw-faf);
        }
        if(know[i] == 1) soln.push_back(i);
    }
	return soln;
}

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