제출 #765626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765626		phoebe	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	116 ms	49764 KiB

garden

#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]));
        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(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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31