oj.uz

Submission #753940

# Submission time Handle Problem Language Result Execution time Memory
753940 2023-06-06T11:06:22 Z lukameladze Tropical Garden (IOI11_garden) C++14
49 / 100
 98 ms 100828 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 = (fin ? (k[i] % fl) : 0), y = (c_in ? (k[i] % sl) : 0);
		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 15 ms 28768 KB Output is correct
3 Correct 14 ms 28732 KB Output is correct
4 Correct 14 ms 28480 KB Output is correct
5 Correct 14 ms 28464 KB Output is correct
6 Correct 15 ms 28756 KB Output is correct
7 Correct 15 ms 28472 KB Output is correct
8 Correct 15 ms 28756 KB Output is correct
9 Correct 16 ms 28928 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28628 KB Output is correct
2 Correct 15 ms 28768 KB Output is correct
3 Correct 14 ms 28732 KB Output is correct
4 Correct 14 ms 28480 KB Output is correct
5 Correct 14 ms 28464 KB Output is correct
6 Correct 15 ms 28756 KB Output is correct
7 Correct 15 ms 28472 KB Output is correct
8 Correct 15 ms 28756 KB Output is correct
9 Correct 16 ms 28928 KB Output is correct
10 Correct 14 ms 28500 KB Output is correct
11 Correct 30 ms 33564 KB Output is correct
12 Correct 47 ms 37144 KB Output is correct
13 Runtime error 98 ms 100828 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 14 ms 28628 KB Output is correct
2 Correct 15 ms 28768 KB Output is correct
3 Correct 14 ms 28732 KB Output is correct
4 Correct 14 ms 28480 KB Output is correct
5 Correct 14 ms 28464 KB Output is correct
6 Correct 15 ms 28756 KB Output is correct
7 Correct 15 ms 28472 KB Output is correct
8 Correct 15 ms 28756 KB Output is correct
9 Correct 16 ms 28928 KB Output is correct
10 Correct 14 ms 28500 KB Output is correct
11 Correct 30 ms 33564 KB Output is correct
12 Correct 47 ms 37144 KB Output is correct
13 Runtime error 98 ms 100828 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -