oj.uz

Submission #53585

# Submission time Handle Problem Language Result Execution time Memory
53585 2018-06-30T09:12:11 Z 강태규(#1417) Regions (IOI09_regions) C++11
28 / 100
 2200 ms 104884 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 = 2;
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
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5624 KB Output is correct
2 Correct 6 ms 5684 KB Output is correct
3 Correct 8 ms 5736 KB Output is correct
4 Correct 10 ms 5864 KB Output is correct
5 Correct 11 ms 5928 KB Output is correct
6 Correct 20 ms 6744 KB Output is correct
7 Correct 29 ms 6744 KB Output is correct
8 Correct 32 ms 6744 KB Output is correct
9 Correct 49 ms 7356 KB Output is correct
10 Incorrect 59 ms 7884 KB Output isn't correct
11 Correct 103 ms 7884 KB Output is correct
12 Incorrect 88 ms 8652 KB Output isn't correct
13 Correct 140 ms 8652 KB Output is correct
14 Correct 163 ms 8652 KB Output is correct
15 Correct 200 ms 10956 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 11468 KB Output is correct
2 Correct 906 ms 11468 KB Output is correct
3 Correct 1190 ms 13476 KB Output is correct
4 Incorrect 189 ms 20264 KB Output isn't correct
5 Incorrect 363 ms 24012 KB Output isn't correct
6 Incorrect 477 ms 30856 KB Output isn't correct
7 Incorrect 806 ms 41316 KB Output isn't correct
8 Incorrect 919 ms 46432 KB Output isn't correct
9 Incorrect 1452 ms 62668 KB Output isn't correct
10 Incorrect 1904 ms 98800 KB Output isn't correct
11 Incorrect 2200 ms 98800 KB Output isn't correct
12 Incorrect 1175 ms 98800 KB Output isn't correct
13 Incorrect 1335 ms 98800 KB Output isn't correct
14 Incorrect 1487 ms 98800 KB Output isn't correct
15 Incorrect 1870 ms 99592 KB Output isn't correct
16 Incorrect 1929 ms 104884 KB Output isn't correct
17 Incorrect 2033 ms 104884 KB Output isn't correct