제출 #429352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429352		2fat2code	Simurgh (IOI17_simurgh)	C++17	100 / 100	184 ms	6152 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)

const int nmax = 505;

int N, m, h[nmax], ansT, royal[nmax*nmax], lipsa[nmax*nmax], pardsu[nmax];
vector<int>T;
pair<int,int>low[nmax], p[nmax];
vector<pair<int,int>>nod[nmax];
bitset<nmax>viz;

void dfstree(int s, int lvl, int par){
    viz[s] = 1;
    h[s] = lvl;
    for(auto it : nod[s]){
        if(!viz[it.fr]){
            T.push_back(it.sc);
            dfstree(it.fr, lvl + 1, s);
            p[it.fr].fr = s;
            p[it.fr].sc = it.sc;
            if(low[it.fr] < low[s]){
                low[s] = low[it.fr];
            }
        }
    }
    for(auto it : nod[s]){
        if(viz[it.fr] && it.fr != par && h[it.fr] < low[s].fr){
            low[s].fr = h[it.fr];
            low[s].sc = it.sc;
        }
    }
}

void calc(vector<int>vecc, int indx){
    reverse(all(vecc));
    vector<int>ask;
    vector<pair<int,int>>Queries;
    for(auto it : vecc){
        if(royal[it] == -1){
            ask.clear();
            for(auto it1 : T){
                if(it1 != it){
                    ask.push_back(it1);
                }
            }
            ask.push_back(indx);
            lipsa[it] = count_common_roads(ask);
            Queries.push_back({lipsa[it], it});
        }
    }
    Queries.push_back({ansT, indx});
    sort(all(Queries));
    if(Queries[0].fr == Queries.back().fr){
        if(Queries.size() == vecc.size() + 1){
            for(auto it : vecc) royal[it] = 0;
        }
        else{
            ask.clear();
            for(auto it : T){
                if(it != vecc[0]){
                    ask.push_back(it);
                }
            }
            ask.push_back(indx);
            int lol = count_common_roads(ask);
            for(auto it : Queries){
                if(it.fr == lol){
                    if(royal[vecc[0]] == 1) royal[it.sc] = 1;
                    else royal[it.sc] = 0;
                }
                else{
                    if(royal[vecc[0]] == 0) royal[it.sc] = 1;
                    else royal[it.sc] = 0;
                }
            }
        }
    }
    else{
        for(auto it : Queries){
            if(it.fr == Queries.back().fr){
                royal[it.sc] = 0;
            }
            else{
                royal[it.sc] = 1;
            }
        }
    }
}

void dfs2(int s){
    viz[s] = 1;
    for(auto it : nod[s]){
        if(it.sc == low[s].sc && low[s].fr < h[s]){
            int curr = s;
            vector<int>vecc;
            while(h[curr] != h[it.fr]){
                vecc.push_back(p[curr].sc);
                curr = p[curr].fr;
            }
            calc(vecc, it.sc);
        }
    }
    for(auto it : nod[s]){
        if(!viz[it.fr]){
            dfs2(it.fr);
        }
    }
}

int findpar(int x){
    if(x != pardsu[x]){
        pardsu[x] = findpar(pardsu[x]);
    }
    return pardsu[x];
}

void unite(int x, int y){
    x = findpar(x);
    y = findpar(y);
    pardsu[x] = y;
}

void make_bs(int s, vector<int>&u, vector<int>&v){
    vector<pair<int,int>>vecc;
    for(auto it : nod[s]){
        if(it.fr != p[s].fr && h[it.fr] < h[s]){
            vecc.push_back({it.fr, it.sc});
        }
    }
    for(int i=0;i<N;i++) pardsu[i] = i;
    vector<int>ask;
    for(auto it : vecc){
        ask.push_back(it.sc);
        unite(s, it.fr);
    }
    int curr = 0;
    for(auto it : T){
        int x = u[it];
        int y = v[it];
        x = findpar(x);
        y = findpar(y);
        if(x != y){
            pardsu[x] = y;
            ask.push_back(it);
            curr -= royal[it];
        }
    }
    curr += count_common_roads(ask);
    int l = 0;
    int r = (int)vecc.size() - 1;
    int lmao = curr;
    for(int j=1;j<=lmao;j++){
        int ok = 0;
        r = (int)vecc.size() - 1;
        while(l <= r){
            ask.clear();
            int mid = l + (r - l) / 2;
            for(int i=0;i<N;i++) pardsu[i] = i;
            for(int i=0;i<=mid;i++){
                ask.push_back(vecc[i].sc);
                unite(s, vecc[i].fr);
            }
            curr = 0;
            for(auto it : T){
                int x = u[it];
                int y = v[it];
                x = findpar(x);
                y = findpar(y);
                if(x != y){
                    pardsu[x] = y;
                    ask.push_back(it);
                    curr -= royal[it];
                }
            }
            curr += count_common_roads(ask);
            if(curr >= j){
                ok = mid;
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        royal[vecc[ok].sc] = 1;
        l = ok + 1;
    }
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	m = (int)u.size();
	N = n;
	for(int i=0;i<m;i++){
        royal[i] = -1;
	}
	for(int i=0;i<n;i++){
        low[i].fr = n + 1;
        low[i].sc = -1;
	}
	for(int i=0;i<m;i++){
        nod[u[i]].push_back({v[i], i});
        nod[v[i]].push_back({u[i], i});
	}
	p[0].fr = -1;
	dfstree(0, 1, -1);
	ansT = count_common_roads(T);
	viz.reset();
	dfs2(0);
	for(auto it : T){
        if(royal[it] == -1) royal[it] = 1;
	}
	for(int i=1;i<n;i++){
        make_bs(i, u, v);
	}
	for(int i=0;i<m;i++){
        if(royal[i] == -1){
            royal[i] = 0;
        }
	}
	vector<int>answer;
	for(int i=0;i<m;i++){
        if(royal[i] == 1)answer.push_back(i);
	}
	return answer;
}

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