제출 #372291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
372291		doowey	Simurgh (IOI17_simurgh)	C++14	100 / 100	157 ms	12072 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];
vector<pii> Q[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);
        }
    }
}

int par[N];
int fin_node(int x){
    if(par[x] == x) return x;
    return par[x]=fin_node(par[x]);
}

bool unite(int a, int b){
    a = fin_node(a);
    b = fin_node(b);
    if(a == b) return false;
    par[a] = b;
    return true;
}

int n;

vector<pii> saf;
vector<int>u,v;

int bins(int l, int r, int val){
    if(val == -1){
        vector<int> E;
        for(int i = 0 ; i < n; i ++ ){
            par[i]=i;
        }
        int rem = 0;
        for(int j = l ; j <= r; j ++ ){
            E.push_back(saf[j].se);
            unite(u[saf[j].se], v[saf[j].se]);
        }
        for(auto x : fq){
            if(unite(u[x], v[x])){
                rem += know[x];
                E.push_back(x);
            }
        }
        val = count_common_roads(E) - rem;
    }
    if(val == 0) return 0;
    if(l == r){
        know[saf[l].se]=1;
        return val;
    }
    int mid = (l + r) / 2;
    int lef = bins(l, mid, -1);
    bins(mid + 1, r, val - lef);
    return val;
}

vector<int> find_roads(int _n, vector<int> u_, vector<int> v_) {
    n = _n;
    u = u_;
    v = 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){
            Q[u[i]].push_back(mp(v[i], i));
        }
    }
    int cnt;
    int cur;
    for(int i = 0 ; i < n; i ++ ){
        if(Q[i].empty()) continue;
        saf = Q[i];
        bins(0, (int)saf.size() - 1, -1);
    }
    for(int i = 0 ; i < m ; i ++ ){
        if(know[i] == 1) soln.push_back(i);
    }
	return soln;
}

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:212:9: warning: unused variable 'cnt' [-Wunused-variable]
  212 |     int cnt;
      |         ^~~
simurgh.cpp:213:9: warning: unused variable 'cur' [-Wunused-variable]
  213 |     int cur;
      |         ^~~

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