oj.uz

Submission #172285

# Submission time Handle Problem Language Result Execution time Memory
172285 2019-12-31T23:47:58 Z qkxwsm Simurgh (IOI17_simurgh) C++14
13 / 100
 54 ms 4728 KB 
#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(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[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);
                    //y = x + ed1 - ed
                    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) ans[i] = 1;
        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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 376 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 3 ms 376 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 376 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 376 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 3 ms 376 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 376 KB correct
14 Correct 4 ms 636 KB correct
15 Correct 5 ms 632 KB correct
16 Incorrect 4 ms 632 KB WA in grader: NO
17 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 376 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 3 ms 376 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 376 KB correct
14 Correct 4 ms 636 KB correct
15 Correct 5 ms 632 KB correct
16 Incorrect 4 ms 632 KB WA in grader: NO
17 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 352 KB correct
3 Incorrect 54 ms 4728 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 376 KB correct
4 Correct 2 ms 376 KB correct
5 Correct 2 ms 376 KB correct
6 Correct 2 ms 376 KB correct
7 Correct 2 ms 376 KB correct
8 Correct 2 ms 376 KB correct
9 Correct 2 ms 376 KB correct
10 Correct 2 ms 376 KB correct
11 Correct 3 ms 376 KB correct
12 Correct 2 ms 376 KB correct
13 Correct 2 ms 376 KB correct
14 Correct 4 ms 636 KB correct
15 Correct 5 ms 632 KB correct
16 Incorrect 4 ms 632 KB WA in grader: NO
17 Halted 0 ms 0 KB -