Submission #70680

#	Time	Username	Problem	Language	Result	Execution time	Memory
70680		aquablitz11	Simurgh (IOI17_simurgh)	C++14	0 / 100	3 ms	492 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 {
            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[fnd] - get_changes(e, fnd);
        }
    } 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;
        }
        for (auto e : path) {
            if (ans[e] == -1)
                ans[e] = ans[ce];
        }
    }
}

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(1, -1);
    defcnt = count_common_roads(T);
    /*for (int i = 0; i < n; ++i) {
        if (low[i].S != -1)
            query_cycle(low[i].S);
    }*/
    
    // test subtask
    for (int i = 0; i < m; ++i) {
        if (!is_tree[i])
            query_cycle(i);
    }

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

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