oj.uz

Submission #753931

# Submission time Handle Problem Language Result Execution time Memory
753931 2023-06-06T10:46:48 Z lukameladze Tropical Garden (IOI11_garden) C++14
49 / 100
 31 ms 36272 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)]]++;
    }
    if (in_cycle) {
        for (int i = cycle_l; i < MX; i++) {
            ans[i] += ans[i - cycle_l];
        }
    }
    in_cycle = 0;
    bfs(cnnt(p));
    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++) answer(ans[k[i]] + ans1[k[i]]);
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31016 KB Output is correct
2 Correct 16 ms 31060 KB Output is correct
3 Correct 19 ms 31116 KB Output is correct
4 Correct 15 ms 29704 KB Output is correct
5 Correct 15 ms 29652 KB Output is correct
6 Correct 17 ms 31060 KB Output is correct
7 Correct 16 ms 30808 KB Output is correct
8 Correct 17 ms 31056 KB Output is correct
9 Correct 20 ms 31320 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31016 KB Output is correct
2 Correct 16 ms 31060 KB Output is correct
3 Correct 19 ms 31116 KB Output is correct
4 Correct 15 ms 29704 KB Output is correct
5 Correct 15 ms 29652 KB Output is correct
6 Correct 17 ms 31060 KB Output is correct
7 Correct 16 ms 30808 KB Output is correct
8 Correct 17 ms 31056 KB Output is correct
9 Correct 20 ms 31320 KB Output is correct
10 Correct 18 ms 30784 KB Output is correct
11 Incorrect 31 ms 36272 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31016 KB Output is correct
2 Correct 16 ms 31060 KB Output is correct
3 Correct 19 ms 31116 KB Output is correct
4 Correct 15 ms 29704 KB Output is correct
5 Correct 15 ms 29652 KB Output is correct
6 Correct 17 ms 31060 KB Output is correct
7 Correct 16 ms 30808 KB Output is correct
8 Correct 17 ms 31056 KB Output is correct
9 Correct 20 ms 31320 KB Output is correct
10 Correct 18 ms 30784 KB Output is correct
11 Incorrect 31 ms 36272 KB Output isn't correct
12 Halted 0 ms 0 KB -