oj.uz

답안 #850301

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
850301 2023-09-16T09:45:23 Z Shreyan_Paliwal Regions (IOI09_regions) C++17
100 / 100
 1792 ms 67472 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 3 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 14 ms 9048 KB Output is correct
7 Correct 21 ms 9048 KB Output is correct
8 Correct 25 ms 9048 KB Output is correct
9 Correct 29 ms 9560 KB Output is correct
10 Correct 44 ms 9420 KB Output is correct
11 Correct 79 ms 9816 KB Output is correct
12 Correct 95 ms 10328 KB Output is correct
13 Correct 93 ms 10124 KB Output is correct
14 Correct 153 ms 10764 KB Output is correct
15 Correct 155 ms 13852 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 717 ms 20128 KB Output is correct
2 Correct 754 ms 18968 KB Output is correct
3 Correct 1216 ms 22204 KB Output is correct
4 Correct 198 ms 10748 KB Output is correct
5 Correct 216 ms 12616 KB Output is correct
6 Correct 446 ms 34660 KB Output is correct
7 Correct 810 ms 31500 KB Output is correct
8 Correct 775 ms 53980 KB Output is correct
9 Correct 1239 ms 18932 KB Output is correct
10 Correct 1522 ms 67472 KB Output is correct
11 Correct 1792 ms 18532 KB Output is correct
12 Correct 648 ms 42000 KB Output is correct
13 Correct 911 ms 42720 KB Output is correct
14 Correct 1206 ms 52612 KB Output is correct
15 Correct 1465 ms 57184 KB Output is correct
16 Correct 1492 ms 64280 KB Output is correct
17 Correct 1461 ms 63440 KB Output is correct