oj.uz

Submission #765625

# Submission time Handle Problem Language Result Execution time Memory
765625 2023-06-24T23:44:30 Z phoebe Tropical Garden (IOI11_garden) C++17
69 / 100
 108 ms 40780 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]));
        sort(ALL(pt.S)); 
        pt.S.resize(distance(pt.S.begin(), unique(ALL(pt.S))));
        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]));
        pt.S.resize(distance(pt.S.begin(), unique(ALL(pt.S))));
        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 10928 KB Output is correct
3 Correct 6 ms 10964 KB Output is correct
4 Correct 6 ms 10848 KB Output is correct
5 Correct 5 ms 10924 KB Output is correct
6 Correct 6 ms 11092 KB Output is correct
7 Correct 5 ms 10836 KB Output is correct
8 Correct 5 ms 10964 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 10928 KB Output is correct
3 Correct 6 ms 10964 KB Output is correct
4 Correct 6 ms 10848 KB Output is correct
5 Correct 5 ms 10924 KB Output is correct
6 Correct 6 ms 11092 KB Output is correct
7 Correct 5 ms 10836 KB Output is correct
8 Correct 5 ms 10964 KB Output is correct
9 Correct 7 ms 11220 KB Output is correct
10 Correct 5 ms 10836 KB Output is correct
11 Correct 16 ms 13652 KB Output is correct
12 Correct 23 ms 15444 KB Output is correct
13 Correct 75 ms 40780 KB Output is correct
14 Correct 76 ms 25984 KB Output is correct
15 Correct 87 ms 26956 KB Output is correct
16 Correct 108 ms 23364 KB Output is correct
17 Correct 67 ms 21748 KB Output is correct
18 Correct 24 ms 15528 KB Output is correct
19 Correct 83 ms 25980 KB Output is correct
20 Correct 88 ms 26896 KB Output is correct
21 Correct 68 ms 22996 KB Output is correct
22 Correct 59 ms 21692 KB Output is correct
23 Correct 86 ms 27468 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 10928 KB Output is correct
3 Correct 6 ms 10964 KB Output is correct
4 Correct 6 ms 10848 KB Output is correct
5 Correct 5 ms 10924 KB Output is correct
6 Correct 6 ms 11092 KB Output is correct
7 Correct 5 ms 10836 KB Output is correct
8 Correct 5 ms 10964 KB Output is correct
9 Correct 7 ms 11220 KB Output is correct
10 Correct 5 ms 10836 KB Output is correct
11 Correct 16 ms 13652 KB Output is correct
12 Correct 23 ms 15444 KB Output is correct
13 Correct 75 ms 40780 KB Output is correct
14 Correct 76 ms 25984 KB Output is correct
15 Correct 87 ms 26956 KB Output is correct
16 Correct 108 ms 23364 KB Output is correct
17 Correct 67 ms 21748 KB Output is correct
18 Correct 24 ms 15528 KB Output is correct
19 Correct 83 ms 25980 KB Output is correct
20 Correct 88 ms 26896 KB Output is correct
21 Correct 68 ms 22996 KB Output is correct
22 Correct 59 ms 21692 KB Output is correct
23 Correct 86 ms 27468 KB Output is correct
24 Incorrect 6 ms 11052 KB Output isn't correct
25 Halted 0 ms 0 KB -