Submission #172257

#	Time	Username	Problem	Language	Result	Execution time	Memory
172257		qkxwsm	Simurgh (IOI17_simurgh)	C++14	13 / 100	147 ms	4756 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;
int eid[MAXN][MAXN];
int dsu[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 findparent(int u)
{
    return (u == dsu[u] ? u : dsu[u] = findparent(dsu[u]));
}
bool merge(int u, int v)
{
    u = findparent(u);
    v = findparent(v);
    if (u == v) return false;
    dsu[u] = v;
    return true;
}

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)
{
    seen[u] = true;
    for (int v : edge[u])
    {
        if (seen[v]) continue;
        parent[v] = u;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

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(u, 0, N)
    {
        for (int v : edge[u])
        {
            int ed = eid[u][v];
            if (v == parent[u] || parent[v] == u) continue;
            //lol there are no side edges.
            if (depth[v] < depth[u]) continue;
            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[eid[u][v]] = x + ans[eid[s][parent[s]]] - y;
            }
        }
    }
    FOR(i, 0, N)
    {
        dsu[i] = i;
    }
    FOR(i, 0, SZ(e1))
    {
        if (ans[i] == 1)
        {
            merge(e1[i], e2[i]);
        }
    }
    FOR(u, 1, N)
    {
        if (ans[eid[u][parent[u]]] == -1)
        {
            ans[eid[u][parent[u]]] = merge(u, parent[u]);
        }
    }
    FOR(i, 0, SZ(e1))
    {
        if (ans[i] == 1) ret.PB(i);
    }
    // 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