oj.uz

Submission #67533

# Submission time Handle Problem Language Result Execution time Memory
67533 2018-08-14T18:08:41 Z imeimi2000 Regions (IOI09_regions) C++17
100 / 100
 3411 ms 105012 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int t = 400;
const int tct = 500;
int n, r, q;
int h[200001];
int s[200001];
vector<int> child[200001];
vector<int> group[25001];
int st[200001];
int ed[200001];
int cnt[25001];
int big[25001];
int rc[25001][t];
int dc[25001][t];
int tp1[t];
int tp2[t];

void dfs(int x) {
    static int ord = 0;
    st[x] = ++ord;
    group[h[x]].push_back(ord);
    if (big[h[x]] != -1) ++tp1[big[h[x]]], ++tp2[big[h[x]]];
    for (int i = 0; i < t; ++i) {
        dc[h[x]][i] -= tp2[i];
    }
    for (int i : child[x]) {
        dfs(i);
    }
    if (big[h[x]] != -1) --tp1[big[h[x]]];
    for (int i = 0; i < t; ++i) {
        rc[h[x]][i] += tp1[i];
        dc[h[x]][i] += tp2[i];
    }
    ed[x] = ord;
    group[h[x]].push_back(-ord);
}

int main() {
    scanf("%d%d%d%d", &n, &r, &q, h + 1);
    for (int i = 2; i <= n; ++i) {
        scanf("%d%d", s + i, h + i);
        child[s[i]].push_back(i);
        ++cnt[h[i]];
    }
    for (int i = 1, j = 0; i <= r; ++i) {
        if (cnt[i] > tct) big[i] = j++;
        else big[i] = -1;
    }
    dfs(1);
    for (int i = 0; i < q; ++i) {
        int r1, r2, ans = 0;
        scanf("%d%d", &r1, &r2);
        
        if (big[r2] != -1) {
            ans = dc[r1][big[r2]];
        }
        else if (big[r1] != -1) {
            ans = rc[r2][big[r1]];
        }
        else {
            int cnt = 0, k = 0, p;
            for (int j : group[r1]) {
                if (j > 0) p = j;
                else p = 1 - j;
                while (k < group[r2].size()) {
                    int x = group[r2][k];
                    if (x > 0) {
                        if (x < p) ans += cnt;
                        else break;
                    }
                    ++k;
                }
                if (j > 0) ++cnt;
                else --cnt;
            }
        }
        
        printf("%d\n", ans);
        fflush(stdout);
    }
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:84:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while (k < group[r2].size()) {
                        ~~^~~~~~~~~~~~~~~~~~
regions.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &r, &q, h + 1);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", s + i, h + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &r1, &r2);
         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5624 KB Output is correct
2 Correct 8 ms 5688 KB Output is correct
3 Correct 9 ms 5892 KB Output is correct
4 Correct 13 ms 5892 KB Output is correct
5 Correct 12 ms 5968 KB Output is correct
6 Correct 23 ms 6640 KB Output is correct
7 Correct 33 ms 6640 KB Output is correct
8 Correct 34 ms 6640 KB Output is correct
9 Correct 52 ms 7324 KB Output is correct
10 Correct 95 ms 7836 KB Output is correct
11 Correct 154 ms 7836 KB Output is correct
12 Correct 150 ms 8628 KB Output is correct
13 Correct 150 ms 8628 KB Output is correct
14 Correct 325 ms 8628 KB Output is correct
15 Correct 313 ms 10804 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1105 ms 11380 KB Output is correct
2 Correct 1125 ms 11380 KB Output is correct
3 Correct 1753 ms 13512 KB Output is correct
4 Correct 218 ms 20156 KB Output is correct
5 Correct 324 ms 24124 KB Output is correct
6 Correct 1056 ms 30780 KB Output is correct
7 Correct 1574 ms 41476 KB Output is correct
8 Correct 1223 ms 46316 KB Output is correct
9 Correct 2720 ms 62752 KB Output is correct
10 Correct 3411 ms 98732 KB Output is correct
11 Correct 3274 ms 98732 KB Output is correct
12 Correct 1308 ms 98732 KB Output is correct
13 Correct 1806 ms 98732 KB Output is correct
14 Correct 2190 ms 98732 KB Output is correct
15 Correct 2827 ms 99640 KB Output is correct
16 Correct 2474 ms 105012 KB Output is correct
17 Correct 2821 ms 105012 KB Output is correct