oj.uz

Submission #753941

# Submission time Handle Problem Language Result Execution time Memory
753941 2023-06-06T11:14:20 Z lukameladze Tropical Garden (IOI11_garden) C++14
100 / 100
 201 ms 67916 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define pb push_back
const int MX = 3e5 + 5;
int n,m,q,p,k[MX],dist[MX],ans[MX], in_cycle, cycle_l,best[MX], s_best[MX],ans1[MX];
vector <int> v[MX], vr[MX],n_g[MX];
vector <pii> g[MX];
int can(int i) {
    return 2 * i - 1;
}
int cnnt(int i) {
    return 2 * i;
}
 
void bfs(int a) {
    queue <int> q;
    int pp = a;
    for (int i = 1; i <= 2 * n; i++) {
        dist[i] = -1;
    }
    q.push(a); dist[a] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int to : vr[x]) {
            if (to == pp) {
                in_cycle = 1;
                cycle_l = dist[x] + 1;
            }
            if (dist[to] == -1) {
                dist[to] = dist[x] + 1;
                q.push(to);
            }
        }
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
	n = N; m = M; p = P; p++; q = Q;
	for (int i = 1; i <= m; i++) {
		int a, b;
		a = R[i - 1][0]; b = R[i - 1][1];
		a++; b++;
		g[a].pb({i - 1, b});
		g[b].pb({i - 1, a});
	}
    for (int i = 1; i <= q; i++) {
        k[i] = G[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end());
        best[i] = g[i][0].s;
        s_best[i] = ((int)g[i].size() == 1 ? g[i][0].s : g[i][1].s);
    }
    for (int i = 1; i <= n; i++) {
        int a = i, b = best[i];
        if (best[b] == a) n_g[can(a)].pb(cnnt(b));
        else n_g[can(a)].pb(can(b));
 
        b = s_best[i];
        if (best[b] == a) n_g[cnnt(a)].pb(cnnt(b));
        else n_g[cnnt(a)].pb(can(b));
    }
    for (int i = 1; i <= n; i++) {
        v[i].clear();
    }
    for (int i = 1; i <= 2 * n; i++) {
        for (int x : n_g[i]) {
//            cout<<i<<" -- "<<x<<"\n";
            v[i].pb(x); vr[x].pb(i);
        }
    }
    bfs(can(p));
    for (int i = 1; i <= n; i++) {
        if (dist[can(i)] == -1) continue;
        ans[dist[can(i)]]++;
    }
    int fin = in_cycle, fl = cycle_l;
/*    if (in_cycle) {
        for (int i = cycle_l; i < MX; i++) {
            ans[i] += ans[i - cycle_l];
        }
    }*/
    in_cycle = 0;
    bfs(cnnt(p));
    int c_in = in_cycle, sl = cycle_l;
    for (int i = 1; i <= n; i++) {
        if (dist[can(i)] == -1) continue;
        ans1[dist[can(i)]]++;
    }
/*    if(in_cycle) {
        for (int i = cycle_l; i < MX; i++) {
            ans1[i] += ans1[i - cycle_l];
        }
    }*/
    n *= 2;
	for(int i = 1; i <= q; i++) {
		int res = 0;
		int x = (fin ? (k[i] % fl) : 0), y = (c_in ? (k[i] % sl) : 0);
		if (k[i] <= n) res += ans[k[i]], res += ans1[k[i]];
		if (fin) {
			for (int j = x; j <= min(k[i], n); j += fl) {
				if (j == k[i]) continue;
				res += ans[j];
			}	
		}
		if (c_in) {
			for (int j = y; j <= min(k[i], n); j += sl) {
				if (j == k[i]) continue;
				res += ans1[j];
			}
		}	
		answer(res);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28628 KB Output is correct
2 Correct 14 ms 28772 KB Output is correct
3 Correct 14 ms 28696 KB Output is correct
4 Correct 14 ms 28536 KB Output is correct
5 Correct 13 ms 28500 KB Output is correct
6 Correct 14 ms 28756 KB Output is correct
7 Correct 13 ms 28500 KB Output is correct
8 Correct 14 ms 28652 KB Output is correct
9 Correct 15 ms 28960 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28628 KB Output is correct
2 Correct 14 ms 28772 KB Output is correct
3 Correct 14 ms 28696 KB Output is correct
4 Correct 14 ms 28536 KB Output is correct
5 Correct 13 ms 28500 KB Output is correct
6 Correct 14 ms 28756 KB Output is correct
7 Correct 13 ms 28500 KB Output is correct
8 Correct 14 ms 28652 KB Output is correct
9 Correct 15 ms 28960 KB Output is correct
10 Correct 13 ms 28500 KB Output is correct
11 Correct 26 ms 33620 KB Output is correct
12 Correct 43 ms 37228 KB Output is correct
13 Correct 63 ms 49836 KB Output is correct
14 Correct 125 ms 58272 KB Output is correct
15 Correct 160 ms 58828 KB Output is correct
16 Correct 123 ms 50028 KB Output is correct
17 Correct 122 ms 47352 KB Output is correct
18 Correct 51 ms 37248 KB Output is correct
19 Correct 137 ms 58472 KB Output is correct
20 Correct 157 ms 58820 KB Output is correct
21 Correct 122 ms 50120 KB Output is correct
22 Correct 115 ms 47280 KB Output is correct
23 Correct 147 ms 61504 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28628 KB Output is correct
2 Correct 14 ms 28772 KB Output is correct
3 Correct 14 ms 28696 KB Output is correct
4 Correct 14 ms 28536 KB Output is correct
5 Correct 13 ms 28500 KB Output is correct
6 Correct 14 ms 28756 KB Output is correct
7 Correct 13 ms 28500 KB Output is correct
8 Correct 14 ms 28652 KB Output is correct
9 Correct 15 ms 28960 KB Output is correct
10 Correct 13 ms 28500 KB Output is correct
11 Correct 26 ms 33620 KB Output is correct
12 Correct 43 ms 37228 KB Output is correct
13 Correct 63 ms 49836 KB Output is correct
14 Correct 125 ms 58272 KB Output is correct
15 Correct 160 ms 58828 KB Output is correct
16 Correct 123 ms 50028 KB Output is correct
17 Correct 122 ms 47352 KB Output is correct
18 Correct 51 ms 37248 KB Output is correct
19 Correct 137 ms 58472 KB Output is correct
20 Correct 157 ms 58820 KB Output is correct
21 Correct 122 ms 50120 KB Output is correct
22 Correct 115 ms 47280 KB Output is correct
23 Correct 147 ms 61504 KB Output is correct
24 Correct 15 ms 28524 KB Output is correct
25 Correct 29 ms 33648 KB Output is correct
26 Correct 45 ms 37208 KB Output is correct
27 Correct 62 ms 49816 KB Output is correct
28 Correct 168 ms 58388 KB Output is correct
29 Correct 201 ms 60680 KB Output is correct
30 Correct 116 ms 51564 KB Output is correct
31 Correct 122 ms 48896 KB Output is correct
32 Correct 51 ms 37836 KB Output is correct
33 Correct 187 ms 60064 KB Output is correct
34 Correct 186 ms 60672 KB Output is correct
35 Correct 116 ms 51604 KB Output is correct
36 Correct 119 ms 48812 KB Output is correct
37 Correct 140 ms 63216 KB Output is correct
38 Correct 119 ms 67916 KB Output is correct