oj.uz

Submission #53587

# Submission time Handle Problem Language Result Execution time Memory
53587 2018-06-30T09:13:18 Z 강태규(#1417) Regions (IOI09_regions) C++11
100 / 100
 2921 ms 104852 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 6 ms 5812 KB Output is correct
3 Correct 8 ms 5812 KB Output is correct
4 Correct 9 ms 5812 KB Output is correct
5 Correct 12 ms 5836 KB Output is correct
6 Correct 23 ms 6732 KB Output is correct
7 Correct 35 ms 6732 KB Output is correct
8 Correct 43 ms 6732 KB Output is correct
9 Correct 84 ms 7368 KB Output is correct
10 Correct 61 ms 7752 KB Output is correct
11 Correct 108 ms 7752 KB Output is correct
12 Correct 120 ms 8652 KB Output is correct
13 Correct 224 ms 8652 KB Output is correct
14 Correct 153 ms 8652 KB Output is correct
15 Correct 248 ms 10988 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1026 ms 11460 KB Output is correct
2 Correct 1068 ms 11460 KB Output is correct
3 Correct 1690 ms 13516 KB Output is correct
4 Correct 385 ms 20172 KB Output is correct
5 Correct 458 ms 24048 KB Output is correct
6 Correct 760 ms 30824 KB Output is correct
7 Correct 1278 ms 41420 KB Output is correct
8 Correct 1129 ms 46404 KB Output is correct
9 Correct 2140 ms 62668 KB Output is correct
10 Correct 2497 ms 98764 KB Output is correct
11 Correct 2855 ms 98764 KB Output is correct
12 Correct 1256 ms 98764 KB Output is correct
13 Correct 1702 ms 98764 KB Output is correct
14 Correct 1967 ms 98764 KB Output is correct
15 Correct 2921 ms 99404 KB Output is correct
16 Correct 2486 ms 104852 KB Output is correct
17 Correct 2377 ms 104852 KB Output is correct