Submission #172289

#	Time	Username	Problem	Language	Result	Execution time	Memory
172289		qkxwsm	Simurgh (IOI17_simurgh)	C++14	13 / 100	149 ms	4608 KiB

simurgh

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

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define MAXN 513

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, T;
int eid[MAXN][MAXN];
int st[MAXN], ft[MAXN];
bitset<MAXN> vis[MAXN];
int rec[MAXN][MAXN];
vi edge[MAXN];
bitset<MAXN> seen;
int parent[MAXN], depth[MAXN];
int ans[MAXN * MAXN];
vi quer;
vi ret;

int get(int a, int b)
{
    if (vis[a][b]) return rec[a][b];
    vis[a][b] = true;
    quer.clear();
    if (a == 0 && b == 0)
    {
        FOR(i, 1, N)
        {
            quer.PB(eid[i][parent[i]]);
        }
        rec[a][b] = count_common_roads(quer);
    }
    else
    {
        FOR(i, 1, N)
        {
            if (i == a) continue;
            quer.PB(eid[i][parent[i]]);
        }
        quer.PB(b);
        rec[a][b] = count_common_roads(quer);
    }
    return rec[a][b];
    //take the tree, except delete a and add edge b.
}

void dfs(int u, int p)
{
    st[u] = T; ft[u] = T;
    T++;
    seen[u] = true;
    for (int v : edge[u])
    {
        if (v == p) continue;
        if (seen[v])
        {
            ckmin(ft[u], st[v]);
            continue;
        }
        parent[v] = u;
        depth[v] = depth[u] + 1;
        dfs(v, u);
        ckmin(ft[u], ft[v]);
    }
}

vi find_roads(int n, vi e1, vi e2)
{
    N = n;
    FOR(i, 0, SZ(e1))
    {
        edge[e1[i]].PB(e2[i]);
        edge[e2[i]].PB(e1[i]);
        eid[e1[i]][e2[i]] = i;
        eid[e2[i]][e1[i]] = i;
        ans[i] = -1;
    }
    parent[0] = N; parent[N] = N;
    dfs(0, N);
    // FOR(i, 1, N)
    // {
    //     cerr << i << " -> " << parent[i] << endl;
    // }
    //1 = yes, -1 = no, 0 = idk
    FOR(i, 0, SZ(e1))
    {
        int u = e1[i], v = e2[i];
        if (depth[u] > depth[v]) swap(u, v);
        if (u == parent[v]) continue;
        int ed = eid[u][v];
        //lol there are no side edges.
        vi nodes; nodes.PB(v);
        while(nodes.back() != u)
        {
            nodes.PB(parent[nodes.back()]);
        }
        //you know the answer?
        int s = -1;
        FOR(i, 0, SZ(nodes) - 1)
        {
            if (ans[eid[nodes[i]][nodes[i + 1]]] != -1)
            {
                s = nodes[i];
                break;
            }
        }
        if (s == -1)
        {
            int mn = get(0, 0), mx = mn;
            FOR(i, 0, SZ(nodes) - 1)
            {
                int x = get(nodes[i], ed);
                ckmin(mn, x);
                ckmax(mx, x);
            }
            FOR(i, 0, SZ(nodes) - 1)
            {
                int x = get(nodes[i], ed);
                ans[eid[nodes[i]][nodes[i + 1]]] = (mn == mx || x == mx ? 0 : 1);
            }
            int x = get(0, 0);
            ans[ed] = (mn == mx || x == mx ? 0 : 1);
        }
        else
        {
            int x = get(s, ed);
            int y = get(0, 0);
            //y +uv - s = x -> uv = x + s - y
            ans[ed] = x + ans[eid[s][parent[s]]] - y;
            FOR(i, 0, SZ(nodes) - 1)
            {
                int ed1 = eid[nodes[i]][nodes[i + 1]];
                if (ans[ed1] != -1) continue;
                x = get(nodes[i], ed);
                //x = y + ed - ed1
                ans[ed1] = y - x + ans[ed];
            }
        }
    }
    FOR(u, 1, N)
    {
        if (ans[eid[u][parent[u]]] == -1)
        {
            ans[eid[u][parent[u]]] = 1;
        }
    }
    FOR(i, 0, SZ(e1))
    {
        if (ans[i] == 1) ret.PB(i);
    }
    assert(SZ(ret) >= N - 1);
    // cerr << "RETURNS:";
    // for (int x : ret)
    // {
    //     cerr << ' ' << x;
    // }
    // cerr << endl;
    return ret;
}

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