Submission #70729

#	Time	Username	Problem	Language	Result	Execution time	Memory
70729		aquablitz11	Simurgh (IOI17_simurgh)	C++14	100 / 100	213 ms	30820 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
 
using pii = pair<int, int>;
#define F first
#define S second

const int N = 510;
const int M = N*(N-1)/2;
const int LIM = 30000;
 
int n, m;
vector<int> U, V; // edge list
vector<pii> G[N]; // adj list
vector<int> T; // tree edges
vector<pii> GT[N]; // tree adj list
bool is_tree[M];

int ans[M]; // answer to each edge (-1 = unknown)
int defcnt; // answer for the default spanning tree

int tick;
pii disc[N], low[N];
void dfs(int u, int p)
{
    disc[u] = low[u] = pii(++tick, -1);
    for (auto v : G[u]) {
        if (!disc[v.F].F) {
            // push edge to tree
            is_tree[v.S] = true;
            T.push_back(v.S);
            GT[u].emplace_back(v.F, v.S);
            GT[v.F].emplace_back(u, v.S);
            // tarjan's algorithm
            dfs(v.F, u);
            low[u] = min(low[u], low[v.F]);
            if (low[v.F].F > disc[u].F)
                ans[v.S] = 1;
        } else if (v.F != p) {
            low[u] = min(low[u], pii(disc[v.F].F, v.S));
        }
    }
}

vector<int> find_path(int u, int e, int t)
{
    if (u == t) {
        vector<int> ret;
        ret.push_back(e);
        return ret;
    }
    for (auto v : GT[u]) if (v.S != e) {
        vector<int> ret = find_path(v.F, v.S, t);
        if (!ret.empty()) {
            if (e != -1)
                ret.push_back(e);
            return ret;
        }
    }
    return vector<int>();
}

int get_changes(int rem, int add)
{
    vector<int> q(T);
    q.erase(find(q.begin(), q.end(), rem));
    q.push_back(add);
    return count_common_roads(q) - defcnt;
}

void query_cycle(int ce)
{
    if (ans[ce] != -1) return;
    int s = U[ce], t = V[ce];
    vector<int> path = find_path(s, -1, t);

    // find edge in path that we already know answer to
    int fnd = -1;
    for (auto e : path) {
        if (ans[e] != -1) {
            fnd = e;
            break;
        }
    }

    if (fnd != -1) { // case where we can quickly determine ce's value
        ans[ce] = ans[fnd] + get_changes(fnd, ce);
        for (auto e : path) { // update other edge in path we don't know
            if (ans[e] == -1)
                ans[e] = ans[ce] - get_changes(e, ce);
        }
    } else { // don't know, so query everything in the cycle
        for (auto e : path) {
            int d = get_changes(e, ce);
            if (d == 1)
                ans[ce] = 1, ans[e] = 0;
            else if (d == -1)
                ans[ce] = 0, ans[e] = 1;
        }
        if (ans[ce] == -1) ans[ce] = 0;
        for (auto e : path) {
            if (ans[e] == -1)
                ans[e] = ans[ce];
        }
    }
}

int par[N];
int root(int u) {
    if (par[u] == u) return u;
    return par[u] = root(par[u]);
}
bool merge(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) return false;
    par[u] = v;
    return true;
}

int query_adj(vector<int> &adj)
{
    if (adj.empty()) return 0;
    iota(par, par+n, 0);
    vector<int> q;
    for (auto e : adj) {
        if (merge(U[e], V[e]))
            q.push_back(e);
    }
    int cnt = 0;
    for (auto e : T) {
        if (merge(U[e], V[e])) {
            cnt += ans[e];
            q.push_back(e);
        }
    }
    int ret = count_common_roads(q);
    return ret-cnt;
}

void solve(vector<int> &adj, int cnt = -1)
{
    if (cnt == -1)
        cnt = query_adj(adj);
    if (cnt == 0) {
        for (auto e : adj)
            ans[e] = 0;
        return;
    }
    if (cnt == adj.size()) {
        for (auto e : adj)
            ans[e] = 1;
        return;
    }

    int mid = adj.size()/2;
    vector<int> L(adj.begin(), adj.begin()+mid);
    vector<int> R(adj.begin()+mid, adj.end());
    int lcnt = query_adj(L);
    solve(L, lcnt);
    solve(R, cnt-lcnt);
}

vector<int> find_roads(int _n, vector<int> _U, vector<int> _V)
{
    // create adj list
    n = _n;
    U = _U, V = _V;
    m = U.size();
    for (int i = 0; i < m; ++i) {
        int u = U[i], v = V[i];
        G[u].emplace_back(v, i);
        G[v].emplace_back(u, i);
    }

    // build dfs tree and find answer for the tree
    fill(ans, ans+m, -1);
    dfs(0, -1);
    defcnt = count_common_roads(T);
    for (int i = 0; i < n; ++i) {
        if (low[i].S != -1)
            query_cycle(low[i].S);
    }

    // find answer for each node
    for (int u = 0; u < n; ++u) {
        vector<int> adj;
        for (auto v : G[u]) {
            if (ans[v.S] == -1)
                adj.push_back(v.S);
        }
        solve(adj);
    }

    // return answer
    vector<int> ret;
    for (int i = 0; i < m; ++i) {
        if (ans[i])
            ret.push_back(i);
    }
    return ret;
}

Compilation message (stderr)

simurgh.cpp: In function 'void solve(std::vector<int>&, int)':
simurgh.cpp:150:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (cnt == adj.size()) {
         ~~~~^~~~~~~~~~~~~

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