Submission #1048327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048327		becaido	Simurgh (IOI17_simurgh)	C++17	51 / 100	687 ms	4840 KiB

simurgh

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#include "grader.cpp"
#else
#include "simurgh.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 505;
const int MSIZ = SIZE * SIZE / 2;

int n, m;
bool ed[MSIZ];
int h[SIZE], pa[SIZE], pid[SIZE];
vector<pair<int, int>> adj[SIZE];

int to[MSIZ], ty[MSIZ];
int dsu(int x) {
    return x == to[x] ? x : (to[x] = dsu(to[x]));
}
void merge(int a, int b) {
    a = dsu(a), b = dsu(b);
    if (a == b) return;
    to[b] = a;
    ty[a] = (ty[a] != 2 ? ty[a] : ty[b]);
}

int que() {
    vector<int> id;
    FOR (i, 0, m - 1) if (ed[i]) id.pb(i);
    // cout << "que : "; for (int i : id) cout << i << ' '; cout << '\n';
    int c = count_common_roads(id);
    // debug(c);
    return c;
}

vector<int> find_roads(int n_, vector<int> u, vector<int> v) {
    n = n_, m = u.size();
    FOR (i, 1, n) {
        adj[i].clear();
        h[i] = pa[i] = pid[i] = -1;
    }
    FOR (i, 0, m - 1) {
        ed[i] = 0;
        u[i]++, v[i]++;
        adj[u[i]].pb(v[i], i);
        adj[v[i]].pb(u[i], i);
    }
    auto dfs = [&](auto dfs, int pos)->void {
        for (auto [np, id] : adj[pos]) if (h[np] == -1) {
            h[np] = h[pos] + 1;
            pa[np] = pos;
            pid[np] = id;
            ed[id] = 1;
            dfs(dfs, np);
        }
    };
    h[1] = 1, dfs(dfs, 1);

    FOR (i, 0, m - 1) {
        to[i] = i;
        ty[i] = 2;
    }
    int tot = que();
    FOR (i, 0, m - 1) if (ed[i] == 0) {
        int x = u[i], y = v[i];
        while (x != y) {
            if (h[x] < h[y]) swap(x, y);
            int j = pid[x];
            if (dsu(i) != dsu(j) && (ty[dsu(i)] == 2 || ty[dsu(j)] == 2)) {
                ed[i] = 1, ed[j] = 0;
                int cur = que();
                if (cur == tot) merge(i, j);
                else {
                    ty[dsu(j)] = (cur > tot ? 0 : 1);
                    ty[dsu(i)] = (cur > tot ? 1 : 0);
                }
                ed[i] = 0, ed[j] = 1;
            }
            x = pa[x];
        }
    }
    vector<int> ans;
    FOR (i, 0, m - 1) if (ty[dsu(i)]) ans.pb(i);
    // cout << "ans : "; for (int i : ans) cout << i << " \n"[i == ans.back()];
    return ans;
}

/*
in1
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/

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