제출 #1290627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290627		mariaclara	Simurgh (IOI17_simurgh)	C++17	100 / 100	376 ms	6048 KiB

simurgh

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n;
vi pai, u, v;
vector<vector<pii>> tree;

int find(int x) {
    if(x == pai[x]) return x;
    return pai[x] = find(pai[x]);
}

void join(int x, int y) {
    pai[find(x)] = pai[find(y)];
}

vi make_tree(vi &edges) {
    for(int i = 0; i < n; i++) pai[i] = i;

    vi T;

    for(int i : edges) {
        if(find(u[i]) == find(v[i])) continue;
        join(u[i], v[i]);
        T.pb(i);
    }

    return T;
}

vi cam, visited;

bool dfs(int x, int y) {
    visited[x] = 1;
    if(x == y) return 1;

    for(auto [viz, id] : tree[x]) {
        if(visited[viz]) continue;

        cam.pb(id);
        if(dfs(viz, y)) return 1;
        cam.pop_back();
    }

    return 0;
}

void call_dfs(int x, int y) {
    cam.clear();
    visited.clear();
    visited.resize(n);
    dfs(x, y);
}

vi operator + (vi &a, vi &b) {
    vi c = a;
    for(auto it : b) c.pb(it);
    return c;
}

vi find_roads(int N, vi U, vi V) {
    n = N; u = U; v = V;
    int m = sz(u);

    tree.resize(n);
    pai.resize(n);

    vi ord(m), tree_set, state(m, -1), pos(m, -1);

    for(int i = 0; i < m; i++) ord[i] = i;
    tree_set = make_tree(ord);

    for(int j = 0, i; j < sz(tree_set); j++) {
        i = tree_set[j];
        pos[i] = j;

        tree[u[i]].pb({v[i], i});
        tree[v[i]].pb({u[i], i});
    }

    int tree_qtd = count_common_roads(tree_set);

    for(int i = 0; i < m; i++) {
        if(pos[i] != -1) continue;

        call_dfs(u[i], v[i]);
        vi rsp;
        int k = -1, calls = 0, max_rsp = tree_qtd;

        for(int j : cam) {
            if(state[j] != -1) {
                rsp.pb(-1);
                k = j;
                continue;
            }

            tree_set[pos[j]] = i;
            int new_qtd = count_common_roads(tree_set); calls++;
            rsp.pb(new_qtd);

            tree_set[pos[j]] = j;
            max_rsp = max(max_rsp, new_qtd);
        }

        if(calls == 0) continue;

        if(k != -1) {
            tree_set[pos[k]] = i;
            int new_qtd = count_common_roads(tree_set);
            tree_set[pos[k]] = k;
            max_rsp = new_qtd + state[k];
        }

        for(int j = 0; j < sz(cam); j++)
            if(state[cam[j]] == -1) state[cam[j]] = rsp[j] != max_rsp;

        state[i] = tree_qtd != max_rsp; 
    }

    vector<vi> edges(n);

    for(int i = 0; i < m; i++) {
        edges[u[i]].pb(i);
        edges[v[i]].pb(i);
        if(pos[i] != -1) state[i] = !!state[i];
    }

    for(int no = 0; no < n; no++) {
        vi no_set, T;
        
        while(1) {
            no_set.clear();
            for(int i : edges[no])
                if(state[i] == -1) no_set.pb(i);

            if(no_set.empty()) break;

            T = no_set + tree_set;
            T = make_tree(T);

            int no_qtd = count_common_roads(T), cnt = 0;
            for(auto it : T) if(pos[it] != -1) cnt += state[it];
            if(cnt == no_qtd) break;

            int l = 0, r = sz(no_set)-1;
            while(l < r) {
                int mid = (l+r)/2;

                T.clear();
                for(int i = l; i <= mid; i++) T.pb(no_set[i]);
                T = T + tree_set;
                T = make_tree(T);

                int no_qtd = count_common_roads(T), cnt = 0;
                for(auto it : T) if(pos[it] != -1) cnt += state[it];
            
                if(cnt == no_qtd) l = mid+1;
                else r = mid;
            }

            for(int i = 0; i < l; i++) state[no_set[i]] = 0;
            state[no_set[l]] = 1;
        }
    }

    vi ans;

    for(int i = 0; i < m; i++)
        if(state[i] == 1) ans.pb(i);

    return ans;
}

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