oj.uz

Submission #299267

# Submission time Handle Problem Language Result Execution time Memory
299267 2020-09-14T15:48:48 Z ToMmyDong Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 76272 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
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;

const int MAXN = 150002*2;
const int MAXLG = 32;
int anc[MAXLG][MAXN];

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;
}

void build () {
    assert(m*2 == SZ(to));
    for (int i=0; i<m*2; i++) {
        anc[0][i] = to[i];
    }

    for (int j=1; j<MAXLG; j++) {
        for (int i=0; i<m*2; i++) {
            anc[j][i] = anc[j-1][anc[j-1][i]];
        }
    }
}
vector<int> g, res, go;
vector<vector<int> > rev;

vector<int> chain;
void make_tree (int nd, int par, int rt) {
    chain.eb(nd);
    debug(nd, chain);
    int sz = SZ(chain);
    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;
                if (ed[chain[sz-1-g[i]]] == p) {
                    debug(i);
                }
            }
        }
    }

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

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;

    srand(time(0));
#ifdef tmdd
    p = rand() % n;
    debug(p);
    for (int i=0; i<Q; i++) {
        G[i] = rand() % 30 + 1;
        debug(G[i]);
    }
    debug(P);
#endif
    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;
    }
    build();
    debug(to);
    debug(start);
    debug(ed);

    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);
        }
    }

    debug(croot, cid, cpos);
    for (int i=0; i<n; i++) {
        vector<pii> qry;
        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];
                assert(csz[id] == csz[rt]);
                int tg = cycle[cid[rt]][(cp + d) % csz[id]];
                res[j] += ed[tg] == p;
                if (ed[tg] == p) {
                    debug(id, j, rt, d, tg, cp);
                }
            }
            qry.eb(d, j);
        }
    }

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

        /*
        int ans = 0;
        for (int x : start) {
            if (dis[x] < G[_]) {
                ans += (G[_] - 1 - dis[x]) % csz[x] == 0;
            }
        }
        */

#ifdef tmd
        int ans = 0;
        for (int x : start) {
            for (int i=0; i<G[_]-1; i++) {
                x = to[x];
            }
            if (ed[x] == p) ans++;
        }
        if (ans != res[_]) {
            debug(G[_], ans, res[_]);
        }
        assert(ans == res[_]);
#endif

        /*
        for (int i=0; i<N; i++) {
            int x = i;
            int prv = -1;
            for (int j=0; j<G[_]; j++) {
                debug(x);
                if (edge[x][0].w != prv || SZ(edge[x]) == 1) {
                    prv = edge[x][0].w;
                    x = edge[x][0].to;
                } else {
                    prv = edge[x][1].w;
                    x = edge[x][1].to;
                }
            }
            debug(i, x);
            ans += x == p;
        }
        */
    }
}


/*
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 2 ms 1152 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 2 ms 1024 KB Output is correct
9 Correct 8 ms 4096 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1152 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 2 ms 1024 KB Output is correct
9 Correct 8 ms 4096 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 26 ms 12672 KB Output is correct
12 Correct 96 ms 26484 KB Output is correct
13 Correct 98 ms 61164 KB Output is correct
14 Correct 329 ms 71532 KB Output is correct
15 Correct 359 ms 74240 KB Output is correct
16 Correct 340 ms 66288 KB Output is correct
17 Correct 306 ms 64884 KB Output is correct
18 Correct 93 ms 25972 KB Output is correct
19 Correct 330 ms 71532 KB Output is correct
20 Correct 377 ms 74220 KB Output is correct
21 Correct 328 ms 66240 KB Output is correct
22 Correct 318 ms 64908 KB Output is correct
23 Correct 355 ms 76272 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1152 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 2 ms 1024 KB Output is correct
9 Correct 8 ms 4096 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 26 ms 12672 KB Output is correct
12 Correct 96 ms 26484 KB Output is correct
13 Correct 98 ms 61164 KB Output is correct
14 Correct 329 ms 71532 KB Output is correct
15 Correct 359 ms 74240 KB Output is correct
16 Correct 340 ms 66288 KB Output is correct
17 Correct 306 ms 64884 KB Output is correct
18 Correct 93 ms 25972 KB Output is correct
19 Correct 330 ms 71532 KB Output is correct
20 Correct 377 ms 74220 KB Output is correct
21 Correct 328 ms 66240 KB Output is correct
22 Correct 318 ms 64908 KB Output is correct
23 Correct 355 ms 76272 KB Output is correct
24 Correct 2 ms 640 KB Output is correct
25 Correct 153 ms 12544 KB Output is correct
26 Correct 208 ms 26612 KB Output is correct
27 Correct 4288 ms 61036 KB Output is correct
28 Correct 1438 ms 71532 KB Output is correct
29 Execution timed out 5031 ms 74256 KB Time limit exceeded
30 Halted 0 ms 0 KB -