제출 #1205493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205493		garam1732	Simurgh (IOI17_simurgh)	C++20	100 / 100	246 ms	5740 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef __int128 i128;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 550;//100100*20;
const ll MOD = 1e9+7;
const ll INF = 2e9;

int par[MAXN];

void init() { for(int i=0; i<MAXN; i++) par[i]=i; }
int root(int x) { return par[x]==x?x:par[x]=root(par[x]); }
void merge(int x, int y) { x = root(x), y = root(y); if(x^y) par[x]=y; }

vector<pi> edge;
vector<pi> adj[MAXN], graph[MAXN];
queue<int> q;
bool vst[MAXN];
pi pv[MAXN];

vector<int> tree;
vector<int> ans;
vector<pi> tmp[MAXN];
bool chk[MAXN*MAXN];

vector<int> input;

int dnc(int x, int s, int e) {
    init(); input.clear();
    for(int i=s; i<=e; i++) {
        input.push_back(adj[x][i].ss);
        merge(x, adj[x][i].ff);
    }

    int res=0;
    for(int t : tree) {
        int a=root(edge[t].ff), b=root(edge[t].ss);
        if(a^b) {
            res -= chk[t];
            input.push_back(t);
            par[a]=b;
        }
    } res += count_common_roads(input);

    if(res == 0) return res;
    if(res == e-s+1) {
        for(int i=s; i<=e; i++) ans.push_back(adj[x][i].ss);
        return res;
    }

//    if(s == e) {
//        ans.push_back(adj[x][s].ss);
//        return;
//    }

    int mid = s+e>>1;
    int z = dnc(x, s, mid);

    if(z < res) dnc(x, mid+1, e);
    return res;
}

void compute(int n, int x) {
    int m = edge.size();
    init(); input.clear();
    for(int i=0; i<m; i++) {
        if(edge[i].ff == x || edge[i].ss == x) continue;
        int a = root(edge[i].ff), b = root(edge[i].ss);
        if(a^b) {
            par[a] = b;
            input.push_back(i);
        }
    }

    for(int i=0; i<n; i++) tmp[i].clear();
    for(auto [y,w] : graph[x]) {
        tmp[root(y)].push_back(pi(0, w));
    }

    for(int i=0; i<n; i++) {
        if(tmp[i].empty()) continue;

        int cnt=0;
        for(int j=0; j<n; j++) {
            if(tmp[j].size() && j!=i) {
                cnt++;
                input.push_back(tmp[j][0].ss);
            }
        }

        for(auto &[y, w] : tmp[i]) {
            input.push_back(w);
            y = count_common_roads(input);
            input.pop_back();
        }

        sort(all(tmp[i]), greater<pi>());
        int t = tmp[i].begin()->ff;
        if(!(t == tmp[i].rbegin()->ff && x && root(pv[x].ff)==i && chk[pv[x].ss]==0))
            for(auto it=tmp[i].begin(); it!=tmp[i].end()&&it->ff==t; it++) chk[it->ss]=1;

        while(cnt--) input.pop_back();
    }
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	int m = u.size();
	for(int i=0; i<m; i++) {
        edge.push_back(pi(u[i], v[i]));
        adj[u[i]].push_back(pi(v[i], i));
        adj[v[i]].push_back(pi(u[i], i));
	}

	// construct bfs-tree and compute for that tree
	q.push(0); vst[0] = 1;
	while(q.size()) {
        int here = q.front(); q.pop();
        for(auto [there,w] : adj[here]) {
            if(vst[there]) continue;

            pv[there] = pi(here, w);
            graph[here].push_back(pi(there, w));
            tree.push_back(w);
            q.push(there); vst[there] = 1;
        }

        if(here) graph[here].push_back(pv[here]);
        compute(n, here);
	}

//	for(int x:tree)cout<<x<<bl;cout<<endl;
//	for(int i=0;i<m;i++) cout<<chk[i]<<bl;cout<<endl;

	for(int i=0; i<n; i++) adj[i].clear();
	for(int i=0; i<m; i++) {
        adj[u[i]].push_back(pi(v[i], i));
	}

	// binary search for each vertex
	for(int x=0; x<n; x++) {
        if(adj[x].size()) dnc(x, 0, (int)adj[x].size()-1);
	} return ans;
}

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