oj.uz

Submission #394251

# Submission time Handle Problem Language Result Execution time Memory
394251 2021-04-26T08:54:22 Z MarcoMeijer Tropical Garden (IOI11_garden) C++14
100 / 100
 1872 ms 41376 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    // create graph
    vector<vi> adj; adj.resize(N);
    int m=0;
    vi U, V, ReverseEdge;
    RE(i,M) {
        U.push_back(R[i][0]); V.push_back(R[i][1]);
        adj[U[m]].push_back(m); ReverseEdge.push_back(m+1); m++;
        U.push_back(R[i][1]); V.push_back(R[i][0]);
        adj[U[m]].push_back(m); ReverseEdge.push_back(m-1); m++;
    }

    // fill next
    vi nxt;
    RE(i,m) {
        bool found = 0;
        FOR(v,adj[V[i]]) {
            if(v == ReverseEdge[i]) continue;
            nxt.push_back(v);
            found = 1;
            break;
        }
        if(!found)
            nxt.push_back(ReverseEdge[i]);
    }

    // fill prev
    vector<vi> prev; prev.resize(m);
    RE(i,m) prev[nxt[i]].pb(i);

    vector<bool> visited;
    visited.assign(m,0);
    vi funct; funct.assign(m,-1);
    vi functRes; functRes.assign(m,-1);

    // iniitial queue
    queue<int> q;
    FOR(x,adj[P]) {
        int y = ReverseEdge[x];
        q.push(y);
        visited[y] = 1;
        funct[y] = 1;
        functRes[y] = nxt[y];
    }

    // bfs
    while(!q.empty()) {
        int u=q.front(); q.pop();
        FOR(v,prev[u]) {
            if(visited[v]) continue;
            q.push(v);
            visited[v] = 1;
            funct[v] = funct[u] + 1;
            functRes[v] = functRes[u];
        }
    }

    map<int,int> Static;
    map<int,map<int,int>> Modulo;
    RE(j,N) {
        int u = adj[j][0];
        int times = 0;
        int cg = 0;
        while(functRes[u] != -1) {
            if(functRes[u] == u) {
                Modulo[funct[u]][cg]++;
                break;
            } else {
                if(functRes[functRes[u]] == u) {
                    int totFunct = funct[u] + funct[functRes[u]];
                    Modulo[totFunct][cg]++;
                    times++;
                    if(times == 2)
                        break;
                }
            }
            cg += funct[u];
            if(functRes[functRes[u]] != u && (functRes[u] == -1 || functRes[functRes[u]] != functRes[u])) {
                Static[cg]++;
            }
            u = functRes[u];
        }
    }
    vector<iii> Mod;
    FOR(x,Modulo)
        FOR(y,x.second)
            Mod.push_back({x.fi,y.fi,y.se});

    RE(i,Q) {
        int ans = 0;
        auto it = Static.find(G[i]);
        if(it != Static.end()) ans += it->second;
        FOR(p,Mod) {
            int a, b, c;
            tie(a,b,c) = p;
            if(G[i] < b) continue;
            if((G[i]-b)%a == 0) ans += c;
        }
        answer(ans);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 5 ms 1360 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 5 ms 1360 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 21 ms 5056 KB Output is correct
12 Correct 39 ms 9964 KB Output is correct
13 Correct 106 ms 29284 KB Output is correct
14 Correct 178 ms 29076 KB Output is correct
15 Correct 203 ms 29972 KB Output is correct
16 Correct 175 ms 25136 KB Output is correct
17 Correct 160 ms 23812 KB Output is correct
18 Correct 40 ms 9900 KB Output is correct
19 Correct 150 ms 29044 KB Output is correct
20 Correct 208 ms 30092 KB Output is correct
21 Correct 173 ms 24920 KB Output is correct
22 Correct 166 ms 23636 KB Output is correct
23 Correct 146 ms 31120 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 5 ms 1360 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 21 ms 5056 KB Output is correct
12 Correct 39 ms 9964 KB Output is correct
13 Correct 106 ms 29284 KB Output is correct
14 Correct 178 ms 29076 KB Output is correct
15 Correct 203 ms 29972 KB Output is correct
16 Correct 175 ms 25136 KB Output is correct
17 Correct 160 ms 23812 KB Output is correct
18 Correct 40 ms 9900 KB Output is correct
19 Correct 150 ms 29044 KB Output is correct
20 Correct 208 ms 30092 KB Output is correct
21 Correct 173 ms 24920 KB Output is correct
22 Correct 166 ms 23636 KB Output is correct
23 Correct 146 ms 31120 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 34 ms 5144 KB Output is correct
26 Correct 42 ms 9924 KB Output is correct
27 Correct 1373 ms 29316 KB Output is correct
28 Correct 158 ms 29076 KB Output is correct
29 Correct 228 ms 30020 KB Output is correct
30 Correct 241 ms 25108 KB Output is correct
31 Correct 169 ms 23720 KB Output is correct
32 Correct 40 ms 9904 KB Output is correct
33 Correct 155 ms 29084 KB Output is correct
34 Correct 201 ms 30012 KB Output is correct
35 Correct 201 ms 24888 KB Output is correct
36 Correct 167 ms 23740 KB Output is correct
37 Correct 168 ms 31196 KB Output is correct
38 Correct 1872 ms 41376 KB Output is correct