oj.uz

Submission #753939

# Submission time Handle Problem Language Result Execution time Memory
753939 2023-06-06T11:05:05 Z lukameladze Tropical Garden (IOI11_garden) C++17
49 / 100
 103 ms 100888 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];
        }
    }*/
	for(int i = 1; i <= q; i++) {
		int res = 0;
		int x = k[i] % fl, y = k[i] % sl;
		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 15 ms 28628 KB Output is correct
2 Correct 16 ms 28768 KB Output is correct
3 Correct 13 ms 28760 KB Output is correct
4 Correct 13 ms 28500 KB Output is correct
5 Correct 15 ms 28544 KB Output is correct
6 Correct 15 ms 28756 KB Output is correct
7 Correct 14 ms 28472 KB Output is correct
8 Correct 14 ms 28720 KB Output is correct
9 Correct 16 ms 28884 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28628 KB Output is correct
2 Correct 16 ms 28768 KB Output is correct
3 Correct 13 ms 28760 KB Output is correct
4 Correct 13 ms 28500 KB Output is correct
5 Correct 15 ms 28544 KB Output is correct
6 Correct 15 ms 28756 KB Output is correct
7 Correct 14 ms 28472 KB Output is correct
8 Correct 14 ms 28720 KB Output is correct
9 Correct 16 ms 28884 KB Output is correct
10 Correct 16 ms 28564 KB Output is correct
11 Correct 27 ms 33620 KB Output is correct
12 Correct 53 ms 37224 KB Output is correct
13 Runtime error 103 ms 100888 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28628 KB Output is correct
2 Correct 16 ms 28768 KB Output is correct
3 Correct 13 ms 28760 KB Output is correct
4 Correct 13 ms 28500 KB Output is correct
5 Correct 15 ms 28544 KB Output is correct
6 Correct 15 ms 28756 KB Output is correct
7 Correct 14 ms 28472 KB Output is correct
8 Correct 14 ms 28720 KB Output is correct
9 Correct 16 ms 28884 KB Output is correct
10 Correct 16 ms 28564 KB Output is correct
11 Correct 27 ms 33620 KB Output is correct
12 Correct 53 ms 37224 KB Output is correct
13 Runtime error 103 ms 100888 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -