oj.uz

답안 #850300

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
850300 2023-09-16T09:45:07 Z Shreyan_Paliwal Regions (IOI09_regions) C++17
100 / 100
 1749 ms 67676 KB 
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = LLONG_MAX / 2 - INT_MAX;

const int maxn = 200005;
const int maxr = 25005;
const int sqrtn = 450;
const int sqrtr = 160;

int n, r, q;
vector<int> adj[maxn];
int re[maxn];

int cnt = 0;
vector<int> sts[maxr], ens[maxr];
int s[maxr], prec[sqrtr][maxr], prec2[maxr][sqrtr], cnt2 = 0;

void dfs(int nd, int par) {
    sts[re[nd]].push_back(cnt++);

    for (auto i : adj[nd])
        if (i != par)
            dfs(i, nd);

    ens[re[nd]].push_back(cnt);
}

int curreg;
int dfs2(int nd, int par, int num) {
    if (re[nd] != curreg) prec[s[curreg]][re[nd]] += num;
    num += re[nd] == curreg;

    int num_current = re[nd] == curreg;
    for (auto i : adj[nd])
        if (i != par)
            num_current += dfs2(i, nd, num);

    if (re[nd] != curreg) prec2[re[nd]][s[curreg]] += num_current;
    return num_current;    
}

int qry(int a, int b) {
    int cnt = 0, num = 0;
    int c1 = 0, c2 = 0, c3 = 0;
    while (c2 < sts[b].size() && c3 < ens[a].size()) {
        int nxt = min(min((c1 < sts[a].size() ? sts[a][c1] : INF), sts[b][c2]), ens[a][c3]);
        if (ens[a][c3] == nxt) { cnt--; c3++; continue; }
        if (c1 < sts[a].size() && sts[a][c1] == nxt) { cnt++; c1++; continue; }
        if (sts[b][c2] == nxt) { num += cnt; c2++; continue; }
    }
    return num;
}

signed main() {
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    fill(s, s+maxr, -1); 

    cin >> n >> r >> q;
    cin >> re[0]; re[0]--;
    for (int i = 1; i < n; i++) 
        { int a; cin >> a >> re[i]; a--, re[i]--; adj[a].push_back(i); }

    dfs(0, 0);
    for (int i = 0; i < r; i++)
        if (sts[i].size() >= sqrtn) {
            s[i] = cnt2++; curreg = i;
            dfs2(0, 0, 0);   
        }

    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b; a--, b--;
        if (s[a] != -1) {cout << prec[s[a]][b] << endl; continue;}
        if (s[b] != -1) {cout << prec2[a][s[b]] << endl; continue;}
        cout << qry(a, b) << endl;
    }
}

Compilation message

regions.cpp: In function 'long long int qry(long long int, long long int)':
regions.cpp:49:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while (c2 < sts[b].size() && c3 < ens[a].size()) {
      |            ~~~^~~~~~~~~~~~~~~
regions.cpp:49:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while (c2 < sts[b].size() && c3 < ens[a].size()) {
      |                                  ~~~^~~~~~~~~~~~~~~
regions.cpp:50:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         int nxt = min(min((c1 < sts[a].size() ? sts[a][c1] : INF), sts[b][c2]), ens[a][c3]);
      |                            ~~~^~~~~~~~~~~~~~~
regions.cpp:52:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         if (c1 < sts[a].size() && sts[a][c1] == nxt) { cnt++; c1++; continue; }
      |             ~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8792 KB Output is correct
4 Correct 4 ms 8792 KB Output is correct
5 Correct 5 ms 8792 KB Output is correct
6 Correct 10 ms 9048 KB Output is correct
7 Correct 19 ms 9048 KB Output is correct
8 Correct 17 ms 9300 KB Output is correct
9 Correct 26 ms 9560 KB Output is correct
10 Correct 51 ms 9304 KB Output is correct
11 Correct 67 ms 9816 KB Output is correct
12 Correct 81 ms 10240 KB Output is correct
13 Correct 92 ms 10144 KB Output is correct
14 Correct 117 ms 10700 KB Output is correct
15 Correct 135 ms 13812 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 602 ms 20128 KB Output is correct
2 Correct 693 ms 18976 KB Output is correct
3 Correct 1098 ms 22204 KB Output is correct
4 Correct 164 ms 10748 KB Output is correct
5 Correct 216 ms 12812 KB Output is correct
6 Correct 403 ms 34488 KB Output is correct
7 Correct 707 ms 31708 KB Output is correct
8 Correct 657 ms 53916 KB Output is correct
9 Correct 1160 ms 18936 KB Output is correct
10 Correct 1573 ms 67676 KB Output is correct
11 Correct 1749 ms 18496 KB Output is correct
12 Correct 725 ms 42000 KB Output is correct
13 Correct 1052 ms 42548 KB Output is correct
14 Correct 1430 ms 52724 KB Output is correct
15 Correct 1626 ms 57304 KB Output is correct
16 Correct 1599 ms 64404 KB Output is correct
17 Correct 1667 ms 63304 KB Output is correct