oj.uz

Submission #299276

# Submission time Handle Problem Language Result Execution time Memory
299276 2020-09-14T15:53:43 Z ToMmyDong Tropical Garden (IOI11_garden) C++17
100 / 100
 4980 ms 59552 KB 
#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx", "avx2", "fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define ALL(i) i.begin(),i.end()
#define SZ(i) int(i.size())
#define X first
#define Y second
#define eb emplace_back
#define pb push_back
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<",";_do(y...);}
template<typename IT> ostream& printRng (ostream& os, IT bg, IT ed) {
    os << "{";
    for (IT it=bg; it!=ed; it++) {
        if (it == bg) os << *it;
        else os << "," << *it;
    }
    return os << "}";
}
template<typename T> ostream& operator << (ostream& os, const vector<T>& v) {return printRng(os,ALL(v));}
template<typename T, typename S> ostream& operator << (ostream& os, const pair<T,S>& v) {return os<<"("<<v.X<<","<<v.Y<<")";}
#else
#define debug(...)
#endif
#include "garden.h"
#include "gardenlib.h"

const int INF = 0x3f3f3f3f;
int n, m, p;
struct Edge {
    int to, w, id;
    bool operator < (const Edge &e) const {
        return w < e.w;
    }
};
vector<int> ed;
vector<vector<Edge>> edge;
vector<int> to, csz, dis, dfn, cdis, croot, cid, cpos;
vector<vector<int>> cycle;


int tme = 0;
int init;
void make_csz (int nd) {
    dfn[nd] = tme++;
    csz[nd] = INF;
    if (csz[to[nd]] == -1) make_csz(to[nd]);
    else if (csz[to[nd]] == INF) {
        if (dfn[to[nd]] >= init) {
            csz[to[nd]] = tme - dfn[to[nd]];
            int y = to[nd];
            vector<int> nc;
            for (int j=0; j<csz[to[nd]]; j++) {
                cpos[y] = SZ(nc);
                nc.eb(y);
                cdis[y] = 0;
                cid[y] = SZ(cycle);
                
                y = to[y];
            }
            cycle.eb(nc);
        }
    }
    csz[nd] = csz[to[nd]];
    if (cdis[nd] != 0) cdis[nd] = cdis[to[nd]] + 1;
}

void make_dis (int nd) {
    dis[nd] = INF;
    if (dis[to[nd]] == -1) make_dis(to[nd]);
    dis[nd] = dis[to[nd]] + 1;
}

vector<int> g, res, go;
vector<vector<int> > rev;

const int MAXN = 150000 * 2 + 5;
int chain[MAXN], ptr;
void make_tree (int nd, int par, int rt) {
    chain[ptr++] = nd;
    int sz = ptr;
    croot[nd] = rt;

    if (go[nd]) {
        for (int i=0; i<SZ(g); i++) {
            if (sz-1-g[i] >= 0) {
                res[i] += ed[chain[sz-1-g[i]]] == p;
            }
        }
    }

    for (int v : rev[nd]) {
        if (v != par && cdis[v] != 0) {
            make_tree(v, nd, rt);
        }
    }
    ptr--;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    edge.resize(N);
    n = N;
    m = M;
    p = P;

    for (int i=0; i<Q; i++) {
        g.eb(G[i]-1);
    }
    int cnt = 0;
    for (int i=0; i<M; i++) {
        int u = R[i][0], v = R[i][1];
        edge[u].pb({v, i, cnt++});
        edge[v].pb({u, i, cnt++});
    }
    ed.resize(cnt);
    rev.resize(cnt);
    for (int i=0; i<n; i++) {
        for (auto e : edge[i]) {
            ed[e.id] = e.to;
        }
    }
    to.resize(cnt), csz.resize(cnt, -1), dis.resize(cnt, -1);
    dfn.resize(cnt, 0);
    cdis.resize(cnt, -1);
    croot.resize(cnt), cid.resize(cnt), cpos.resize(cnt);
    for (int i=0; i<n; i++) {
        sort(ALL(edge[i]));
    }

    vector<int> start;
    go.resize(cnt);
    for (int i=0; i<n; i++) {
        for (const Edge &e : edge[i]) {
            int x = e.to;
            if (x == p) dis[e.id] = 0;
            if (SZ(edge[x]) == 1) {
                to[e.id] = edge[x][0].id;
            } else {
                to[e.id] = edge[x][edge[x][0].w == e.w ? 1 : 0].id;
            }
            rev[to[e.id]].eb(e.id);
        }
        start.eb(edge[i][0].id);
        go[edge[i][0].id] = true;
    }

    for (int i=0; i<cnt; i++) {
        if (csz[i] == -1) {
            init = tme;
            make_csz(i);
        }
    }
    debug(cdis, csz);
    for (int i=0; i<cnt; i++) {
        if (dis[i] == -1) {
            make_dis(i);
        }
    }

    res.resize(Q);
    debug(cycle, cdis);
    for (auto &v : cycle) {
        for (int r : v) {
            make_tree(r, -1, r);
        }
    }

    for (int i=0; i<n; i++) {
        if (dis[edge[i][0].id] >= INF) continue;
        for (int j=0; j<Q; j++) {
            int id = edge[i][0].id;
            int d = G[j] - 1;
            if (d > cdis[id]) {
                d = (d-cdis[id]) % csz[id];
                int rt = croot[id];
                int cp = cpos[rt];
                int tg = cycle[cid[rt]][(cp + d) % csz[id]];
                res[j] += ed[tg] == p;
            }
        }
    }

    for (int _=0; _<Q; _++) {
        answer(res[_]);
    }
}


/*
6 5 2
1 3
0 1
1 2
3 4
3 5
5
32 4 2 1 23 
0 0 0 0 0
 */

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 1024 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 6 ms 1920 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 1024 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 6 ms 1920 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 22 ms 6784 KB Output is correct
12 Correct 82 ms 13172 KB Output is correct
13 Correct 79 ms 44780 KB Output is correct
14 Correct 291 ms 36080 KB Output is correct
15 Correct 320 ms 37364 KB Output is correct
16 Correct 285 ms 32240 KB Output is correct
17 Correct 271 ms 30452 KB Output is correct
18 Correct 81 ms 12536 KB Output is correct
19 Correct 297 ms 36080 KB Output is correct
20 Correct 315 ms 37360 KB Output is correct
21 Correct 289 ms 31728 KB Output is correct
22 Correct 275 ms 30448 KB Output is correct
23 Correct 308 ms 38636 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 1024 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 6 ms 1920 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 22 ms 6784 KB Output is correct
12 Correct 82 ms 13172 KB Output is correct
13 Correct 79 ms 44780 KB Output is correct
14 Correct 291 ms 36080 KB Output is correct
15 Correct 320 ms 37364 KB Output is correct
16 Correct 285 ms 32240 KB Output is correct
17 Correct 271 ms 30452 KB Output is correct
18 Correct 81 ms 12536 KB Output is correct
19 Correct 297 ms 36080 KB Output is correct
20 Correct 315 ms 37360 KB Output is correct
21 Correct 289 ms 31728 KB Output is correct
22 Correct 275 ms 30448 KB Output is correct
23 Correct 308 ms 38636 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 107 ms 6912 KB Output is correct
26 Correct 157 ms 13300 KB Output is correct
27 Correct 2414 ms 45036 KB Output is correct
28 Correct 1234 ms 36336 KB Output is correct
29 Correct 4597 ms 37232 KB Output is correct
30 Correct 2899 ms 32112 KB Output is correct
31 Correct 2680 ms 30576 KB Output is correct
32 Correct 179 ms 12660 KB Output is correct
33 Correct 1241 ms 36080 KB Output is correct
34 Correct 4624 ms 37232 KB Output is correct
35 Correct 3023 ms 31764 KB Output is correct
36 Correct 2671 ms 30452 KB Output is correct
37 Correct 939 ms 38892 KB Output is correct
38 Correct 4980 ms 59552 KB Output is correct