oj.uz

Submission #765624

# Submission time Handle Problem Language Result Execution time Memory
765624 2023-06-24T23:35:26 Z phoebe Tropical Garden (IOI11_garden) C++17
69 / 100
 124 ms 41876 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

#define pii pair<int, int>
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

const int maxn = 150051;
int n, m, p, dist1[maxn * 2], dist2[maxn * 2], 
// dist1 = best, dist2 = 2nd best
dist3[maxn * 2],
r[maxn * 2], cycle1 = -1, cycle2 = -1;
vector<pii> adj[maxn];
vector<int> adj2[maxn * 2]; 
// i * 2 = incoming is not best, leads to best
// i * 2 + 1 = incoming is best, leads to second best

map<int, vector<int>> mp1, mp2, ans1, ans2;
// make functional group
map<int, int> re;

void bfs(){
    queue<int> q; q.push(p * 2); dist1[p * 2] = 0;
    while (!q.empty()){
        int v = q.front(); q.pop();
        for (auto u : adj2[v]){
            if (dist1[u] != -1) continue;
            dist1[u] = dist1[v] + 1;
            q.push(u);
        }
    }
    q.push(p * 2 + 1); dist2[p * 2 + 1] = 0;
    while (!q.empty()){
        int v = q.front(); q.pop();
        for (auto u : adj2[v]){
            if (dist2[u] != -1) continue;
            dist2[u] = dist2[v] + 1;
            q.push(u);
        }
    }
}

void get_cycle(){
    int v = p * 2; 
    fill(dist3, dist3 + n * 2, -1); dist3[p * 2] = 0;
    while (true){
        if (dist3[r[v]] != -1) break;
        dist3[r[v]] = dist3[v] + 1;
        v = r[v];
    }
    if (r[v] == p * 2){ // has cycle
        cycle1 = dist3[v] + 1;
    }
    // for (int i = 0; i < n * 2; i++) cout << dist3[i * 2] << ' '; cout << endl;
    v = p * 2 + 1;
    fill(dist3, dist3 + n * 2, -1); dist3[p * 2 + 1] = 0;
    while (true){
        if (dist3[r[v]] != -1) break;
        dist3[r[v]] = dist3[v] + 1;
        v = r[v];
    }
    if (r[v] == p * 2 + 1){ // has cycle
        cycle2 = dist3[v] + 1;
    }
    // for (int i = 0; i < n * 2; i++) cout << dist3[i * 2] << ' '; cout << endl;
}

void solve(){
    for (auto &pt : ans1){
        int x = pt.F; sort(ALL(mp1[x]));
        for (auto g : pt.S){
            int cnt = upper_bound(ALL(mp1[x]), g) - mp1[x].begin();
            re[g] += cnt;
        }
    }
    for (auto &pt : ans2){
        int x = pt.F; sort(ALL(mp2[x]));
        for (auto g : pt.S){
            int cnt = upper_bound(ALL(mp2[x]), g) - mp2[x].begin();
            re[g] += cnt;
        }
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    n = N, m = M, p = P;
    for (int i = 0; i < m; i++){
        adj[R[i][0]].push_back({i, R[i][1]});
        adj[R[i][1]].push_back({i, R[i][0]});
    }
    for (int v = 0; v < n; v++){
        sort(adj[v].begin(), adj[v].end());
    }
    for (int v = 0; v < n; v++){
        int best = adj[v][0].second;
        int bests_best = adj[best][0].second;
        // cout << v << ' ' << best << ' ' << adj[v].size() << endl;
        if (v != bests_best){
            adj2[best * 2].push_back(v * 2);
            r[v * 2] = best * 2;
        }
        else{
            adj2[best * 2 + 1].push_back(v * 2);
            // adj2[v * 2 + 1].push_back(best * 2);
            r[v * 2] = best * 2 + 1;
        }
        int second_best = adj[v][min((int)adj[v].size() - 1, 1)].second;
        int second_bests_best = adj[second_best][0].second;
        // cout << v << ' ' << second_best << endl;
        if (v != second_bests_best){
            adj2[second_best * 2].push_back(v * 2 + 1);
            r[v * 2 + 1] = second_best * 2;
        }
        else{
            adj2[second_best * 2 + 1].push_back(v * 2 + 1);
            r[v * 2 + 1] = second_best * 2 + 1;
        }
    }
    // for (int i = 0; i < n * 2; i++) cout << r[i] << ' '; cout << endl;
    fill(dist1, dist1 + n * 2, -1);
    fill(dist2, dist2 + n * 2, -1);
    bfs();
    get_cycle();
    // cout << cycle1 << ' ' << cycle2 << endl;
    // return;
    for (int v = 0; v < n; v++){
        // if (v == p) continue;
        if (dist1[v * 2] != -1){
            if (cycle1 == -1) mp1[dist1[v * 2]].push_back(dist1[v * 2]);
            else mp1[dist1[v * 2] % cycle1].push_back(dist1[v * 2]);
        }
        if (dist2[v * 2] != -1){
            if (cycle2 == -1) mp2[dist2[v * 2]].push_back(dist2[v * 2]);
            else mp2[dist2[v * 2] % cycle2].push_back(dist2[v * 2]);
        }
    }

    // return;
    for (int i = 0; i < Q; i++){
        if (cycle1 == -1) ans1[G[i]].push_back(G[i]);
        else ans1[G[i] % cycle1].push_back(G[i]);
        if (cycle2 == -1) ans2[G[i]].push_back(G[i]);
        else ans2[G[i] % cycle2].push_back(G[i]);
    }
    solve();
    // for (int i = 0; i < 5; i++) cout << re[i] << ' '; cout << endl;
    // cout << "bruh" << endl;
    for (int i = 0; i < Q; i++) {
        // cout << re[G[i]] << ' '; cout << endl;
        answer(re[G[i]]);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10964 KB Output is correct
2 Correct 6 ms 10964 KB Output is correct
3 Correct 6 ms 11020 KB Output is correct
4 Correct 8 ms 10880 KB Output is correct
5 Correct 5 ms 10836 KB Output is correct
6 Correct 6 ms 11024 KB Output is correct
7 Correct 5 ms 10884 KB Output is correct
8 Correct 6 ms 11020 KB Output is correct
9 Correct 7 ms 11220 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10964 KB Output is correct
2 Correct 6 ms 10964 KB Output is correct
3 Correct 6 ms 11020 KB Output is correct
4 Correct 8 ms 10880 KB Output is correct
5 Correct 5 ms 10836 KB Output is correct
6 Correct 6 ms 11024 KB Output is correct
7 Correct 5 ms 10884 KB Output is correct
8 Correct 6 ms 11020 KB Output is correct
9 Correct 7 ms 11220 KB Output is correct
10 Correct 6 ms 10880 KB Output is correct
11 Correct 14 ms 13844 KB Output is correct
12 Correct 25 ms 15976 KB Output is correct
13 Correct 74 ms 41876 KB Output is correct
14 Correct 80 ms 27716 KB Output is correct
15 Correct 117 ms 28732 KB Output is correct
16 Correct 77 ms 24884 KB Output is correct
17 Correct 80 ms 23304 KB Output is correct
18 Correct 25 ms 16084 KB Output is correct
19 Correct 77 ms 27624 KB Output is correct
20 Correct 124 ms 28796 KB Output is correct
21 Correct 74 ms 24588 KB Output is correct
22 Correct 65 ms 23152 KB Output is correct
23 Correct 87 ms 29260 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10964 KB Output is correct
2 Correct 6 ms 10964 KB Output is correct
3 Correct 6 ms 11020 KB Output is correct
4 Correct 8 ms 10880 KB Output is correct
5 Correct 5 ms 10836 KB Output is correct
6 Correct 6 ms 11024 KB Output is correct
7 Correct 5 ms 10884 KB Output is correct
8 Correct 6 ms 11020 KB Output is correct
9 Correct 7 ms 11220 KB Output is correct
10 Correct 6 ms 10880 KB Output is correct
11 Correct 14 ms 13844 KB Output is correct
12 Correct 25 ms 15976 KB Output is correct
13 Correct 74 ms 41876 KB Output is correct
14 Correct 80 ms 27716 KB Output is correct
15 Correct 117 ms 28732 KB Output is correct
16 Correct 77 ms 24884 KB Output is correct
17 Correct 80 ms 23304 KB Output is correct
18 Correct 25 ms 16084 KB Output is correct
19 Correct 77 ms 27624 KB Output is correct
20 Correct 124 ms 28796 KB Output is correct
21 Correct 74 ms 24588 KB Output is correct
22 Correct 65 ms 23152 KB Output is correct
23 Correct 87 ms 29260 KB Output is correct
24 Incorrect 6 ms 11020 KB Output isn't correct
25 Halted 0 ms 0 KB -