oj.uz

Submission #299124

# Submission time Handle Problem Language Result Execution time Memory
299124 2020-09-14T13:50:54 Z ToMmyDong Tropical Garden (IOI11_garden) C++17
49 / 100
 59 ms 15600 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));}
#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;

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]];
        }
    }
    csz[nd] = csz[to[nd]];
}

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

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    edge.resize(N);
    n = N;
    m = N;
    p = P;
    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);
    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);
    for (int i=0; i<n; i++) {
        sort(ALL(edge[i]));
    }

    vector<int> start;
    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;
            }
        }
        start.eb(edge[i][0].id);
    }
    debug(to);
    debug(start);
    debug(ed);

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

    for (int _=0; _<Q; _++) {

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

        /*
        for (int x : start) {
            for (int i=0; i<G[_]-1; i++) {
                x = to[x];
            }
            debug(ed[x], p);
            if (ed[x] == p) ans++;
        }
        */

        /*
        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;
        }
        */
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 1032 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 12 ms 3184 KB Output is correct
12 Correct 34 ms 6892 KB Output is correct
13 Incorrect 59 ms 15600 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 4 ms 1032 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 12 ms 3184 KB Output is correct
12 Correct 34 ms 6892 KB Output is correct
13 Incorrect 59 ms 15600 KB Output isn't correct
14 Halted 0 ms 0 KB -