oj.uz

Submission #707296

# Submission time Handle Problem Language Result Execution time Memory
707296 2023-03-08T18:06:32 Z Nhoksocqt1 Tropical Garden (IOI11_garden) C++17
69 / 100
 307 ms 61712 KB 
#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 150005;
const int MAXM = 300005;

struct Edge {
    int u, v;
} edge[MAXN];

struct Query {
    int K, pos;
} qr[2005];

vector<ii> adj[MAXN];
vector<int> adjp[MAXM], comp[MAXM], B[MAXM];
ii a[MAXM], b[MAXM], itOf[MAXM];
int h[MAXM], timeIn[MAXM], timeOut[MAXM], result[2005];
int firstToLoop[MAXM], firstInLoop[MAXM], loopOf[MAXM], posInComp[MAXM];
int deg[MAXM], pa[MAXM], idc[MAXM], idn[MAXN], numNode, numEdge, numQuery, lastNode;
bool dx[MAXM], ok[MAXM];

inline int getLeftNode(int id) {
    return (id >= numEdge) ? edge[id - numEdge].v : edge[id].u;
}

int timeIn0;
void preDfs(int u, int p) {
    timeIn[u] = ++timeIn0;
    if(ok[u])
        B[h[u]].push_back(timeIn[u]);

    for (int it = 0; it < int(adjp[u].size()); ++it) {
        int v(adjp[u][it]);
        if(v != p) {
            h[v] = 1 + h[u];
            preDfs(v, u);
        }
    }

    timeOut[u] = timeIn0;
}

void count_routes(int _N, int _M, int _P, int _R[][2], int _Q, int _G[]) {
    numNode = _N, numEdge = _M, lastNode = _P, numQuery = _Q;
    for (int i = 0; i < _M; ++i) {
        int u(_R[i][0]), v(_R[i][1]);
        edge[i] = {u, v};
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    for (int u = 0; u < numNode; ++u) {
        int id0 = adj[u][0].se;
        int id1 = (adj[u].size() > 1 ? adj[u][1].se : 1e9+7);
        bool type0 = (u == edge[adj[u][0].se].v);
        bool type1 = (adj[u].size() > 1 && (u == edge[adj[u][1].se].v));

        for (int it = 0; it < int(adj[u].size()); ++it) {
            int v(adj[u][it].fi), id(adj[u][it].se);
            bool type = !(u == edge[id].v);
            if(it == 0) {
                idn[u] = id + !type * numEdge;
                ok[idn[u]] = 1;
            }

            pa[id + type * numEdge] = (id != id0 || id1 >= 1e9+7) ? id0 + type0 * numEdge : id1 + type1 * numEdge;
            ++deg[pa[id + type * numEdge]];
        }
    }

    int numComp(0);
    for (int id = 0; id < 2 * numEdge; ++id) {
        if(deg[id] || dx[id])
            continue;

        vector<int> tmpn;
        int tmp(id);
        while(!dx[tmp]) {
            dx[tmp] = 1;
            tmpn.push_back(tmp);
            tmp = pa[tmp];
        }

        int szn(tmpn.size());
        for (int it = 0; it <= szn; ++it) {
            if(it == szn || tmpn[it] == tmp) {
                if(it < szn) {
                    for (int jt = it; jt < szn; ++jt) {
                        posInComp[tmpn[jt]] = jt - it;
                        comp[numComp].push_back(tmpn[jt]);
                        firstInLoop[tmpn[jt]] = tmpn[jt];
                        loopOf[tmpn[jt]] = szn - it;
                        firstToLoop[tmpn[jt]] = 0;
                        idc[tmpn[jt]] = numComp;
                    }

                    ++numComp;
                }

                if(it > 0) {
                    adjp[tmp].push_back(tmpn[it - 1]);
                    for (int jt = 0; jt < it; ++jt) {
                        posInComp[tmpn[jt]] = jt;
                        comp[numComp].push_back(tmpn[jt]);
                        firstToLoop[tmpn[jt]] = it - jt + firstToLoop[tmp];
                        firstInLoop[tmpn[jt]] = firstInLoop[tmp];
                        idc[tmpn[jt]] = numComp;
                        if(jt + 1 < it)
                            adjp[tmpn[jt + 1]].push_back(tmpn[jt]);
                    }

                    ++numComp;
                }

                break;
            }
        }
    }

    for (int id = 0; id < 2 * numEdge; ++id) {
        if(!deg[id] || dx[id])
            continue;

        int tmp(id);
        while(!dx[tmp]) {
            dx[tmp] = 1;
            posInComp[tmp] = comp[numComp].size();
            comp[numComp].push_back(tmp);
            idc[tmp] = numComp;
            firstToLoop[tmp] = 0;
            firstInLoop[tmp] = tmp;
            tmp = pa[tmp];
        }

        int szn(comp[numComp].size());
        for (int it = 0; it < szn; ++it)
            loopOf[comp[numComp][it]] = szn;

        ++numComp;
    }

    for (int id = 0; id < 2 * numEdge; ++id) {
        if(!timeIn[id])
            preDfs(id, -1);

        a[id] = {timeIn[id], id};
        b[id] = {timeOut[id], id};
    }

    for (int t = 0; t < numQuery; ++t)
        qr[t] = {_G[t], t};

    sort(qr, qr + numQuery, [](const Query &a, const Query &b) {
        return a.K < b.K;
    });

    sort(a, a + 2 * numEdge);
    sort(b, b + 2 * numEdge);

    for (int itn = 0; itn < 2 * numEdge; ++itn) {
        int id(a[itn].se);
        if(adjp[id].size() == 0 || getLeftNode(id) != lastNode)
            continue;

        for (int t = 0; t < numQuery; ++t) {
            int K(_G[t]), pos(qr[t].pos);
            if(h[id] + K > 2 * numEdge || B[h[id] + K].empty())
                break;

            h[id] += K;
            int szB(B[h[id]].size());
            while(itOf[h[id]].fi < szB && B[h[id]][itOf[h[id]].fi] <= timeOut[id])
                ++itOf[h[id]].fi;

            result[pos] += itOf[h[id]].fi;
            h[id] -= K;
        }
    }

    for (int itn = 0; itn < 2 * numEdge; ++itn) {
        int id(b[itn].se);
        if(adjp[id].size() == 0 || getLeftNode(id) != lastNode)
            continue;

        for (int t = 0; t < numQuery; ++t) {
            int K(qr[t].K), pos(qr[t].pos);
            if(h[id] + K > 2 * numEdge || B[h[id] + K].empty())
                break;

            h[id] += K;
            int szB(B[h[id]].size());
            while(itOf[h[id]].se < szB && B[h[id]][itOf[h[id]].se] < timeIn[id])
                ++itOf[h[id]].se;

            result[pos] -= itOf[h[id]].se;
            h[id] -= K;
        }
    }

    for (int t = 0; t < numQuery; ++t) {
        int K(qr[t].K), pos(qr[t].pos);
        for (int u = 0; u < numNode; ++u) {
            if(firstToLoop[idn[u]] >= K)
                continue;

            int id(firstInLoop[idn[u]]), posn = (posInComp[id] + K - firstToLoop[idn[u]]) % loopOf[id];
            result[pos] += (getLeftNode(comp[idc[id]][posn]) == lastNode);
        }
    }

    for (int t = 0; t < numQuery; ++t) {
        //cout << result[t] << '\n';
        answer(result[t]);
    }
}

Compilation message

garden.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("O3")
      | 
garden.cpp:9: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    9 | #pragma GCC optimization ("unroll-loops")
      | 
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:82:17: warning: unused variable 'v' [-Wunused-variable]
   82 |             int v(adj[u][it].fi), id(adj[u][it].se);
      |                 ^

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25300 KB Output is correct
2 Correct 14 ms 25244 KB Output is correct
3 Correct 16 ms 25332 KB Output is correct
4 Correct 13 ms 24984 KB Output is correct
5 Correct 13 ms 24980 KB Output is correct
6 Correct 14 ms 25636 KB Output is correct
7 Correct 15 ms 25172 KB Output is correct
8 Correct 14 ms 25232 KB Output is correct
9 Correct 20 ms 26792 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25300 KB Output is correct
2 Correct 14 ms 25244 KB Output is correct
3 Correct 16 ms 25332 KB Output is correct
4 Correct 13 ms 24984 KB Output is correct
5 Correct 13 ms 24980 KB Output is correct
6 Correct 14 ms 25636 KB Output is correct
7 Correct 15 ms 25172 KB Output is correct
8 Correct 14 ms 25232 KB Output is correct
9 Correct 20 ms 26792 KB Output is correct
10 Correct 13 ms 25000 KB Output is correct
11 Correct 30 ms 30012 KB Output is correct
12 Correct 81 ms 37500 KB Output is correct
13 Correct 50 ms 40700 KB Output is correct
14 Correct 275 ms 60416 KB Output is correct
15 Correct 292 ms 61588 KB Output is correct
16 Correct 259 ms 57228 KB Output is correct
17 Correct 228 ms 56756 KB Output is correct
18 Correct 93 ms 38164 KB Output is correct
19 Correct 281 ms 60268 KB Output is correct
20 Correct 299 ms 61680 KB Output is correct
21 Correct 307 ms 58160 KB Output is correct
22 Correct 251 ms 56832 KB Output is correct
23 Correct 265 ms 61712 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25300 KB Output is correct
2 Correct 14 ms 25244 KB Output is correct
3 Correct 16 ms 25332 KB Output is correct
4 Correct 13 ms 24984 KB Output is correct
5 Correct 13 ms 24980 KB Output is correct
6 Correct 14 ms 25636 KB Output is correct
7 Correct 15 ms 25172 KB Output is correct
8 Correct 14 ms 25232 KB Output is correct
9 Correct 20 ms 26792 KB Output is correct
10 Correct 13 ms 25000 KB Output is correct
11 Correct 30 ms 30012 KB Output is correct
12 Correct 81 ms 37500 KB Output is correct
13 Correct 50 ms 40700 KB Output is correct
14 Correct 275 ms 60416 KB Output is correct
15 Correct 292 ms 61588 KB Output is correct
16 Correct 259 ms 57228 KB Output is correct
17 Correct 228 ms 56756 KB Output is correct
18 Correct 93 ms 38164 KB Output is correct
19 Correct 281 ms 60268 KB Output is correct
20 Correct 299 ms 61680 KB Output is correct
21 Correct 307 ms 58160 KB Output is correct
22 Correct 251 ms 56832 KB Output is correct
23 Correct 265 ms 61712 KB Output is correct
24 Incorrect 15 ms 25136 KB Output isn't correct
25 Halted 0 ms 0 KB -