oj.uz

Submission #53533

# Submission time Handle Problem Language Result Execution time Memory
53533 2018-06-30T07:30:55 Z 강태규(#1417) Regions (IOI09_regions) C++11
15 / 100
 8000 ms 24652 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;

int n, r, q;
int h[200001];
int s[200001];
vector<int> child[200001];
int st[200001];
int ed[200001];
vector<int> sum[25001];
vector<int> mn[25001];
map<pii, int> mp;

void dfs(int x) {
    static int ord = 0;
    st[x] = ++ord;
    sum[h[x]].push_back(ord);
    for (int i : child[x]) {
        dfs(i);
    }
    ed[st[x]] = ord;
    mn[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);
    }
    dfs(1);
    for (int i = 0; i < q; ++i) {
        int r1, r2, ans = 0;
        scanf("%d%d", &r1, &r2);
        map<pii, int>::iterator it = mp.find(pii(r1, r2));
        if (it != mp.end()) ans = it->second;
        else if (sum[r1].size() < sum[r2].size()) {
            for (int j : sum[r1]) {
                ans += lower_bound(sum[r2].begin(), sum[r2].end(), ed[j] + 1)
                    - lower_bound(sum[r2].begin(), sum[r2].end(), j);
            }
        }
        else {
            for (int j : sum[r2]) {
                ans += lower_bound(sum[r1].begin(), sum[r1].end(), j + 1) - sum[r1].begin();
                ans -= lower_bound(mn[r1].begin(), mn[r1].end(), j) - mn[r1].begin();
            }
        }
        printf("%d\n", ans);
        fflush(stdout);
    }
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:43: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:45: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:51: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 6136 KB Output is correct
2 Correct 7 ms 6324 KB Output is correct
3 Correct 10 ms 6324 KB Output is correct
4 Correct 10 ms 6352 KB Output is correct
5 Correct 13 ms 6376 KB Output is correct
6 Correct 29 ms 6420 KB Output is correct
7 Correct 32 ms 6548 KB Output is correct
8 Correct 34 ms 6584 KB Output is correct
9 Correct 48 ms 6968 KB Output is correct
10 Correct 85 ms 6988 KB Output is correct
11 Correct 124 ms 7244 KB Output is correct
12 Correct 139 ms 7756 KB Output is correct
13 Correct 183 ms 7756 KB Output is correct
14 Correct 315 ms 8140 KB Output is correct
15 Correct 309 ms 10060 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8023 ms 11084 KB Time limit exceeded
2 Execution timed out 8006 ms 11084 KB Time limit exceeded
3 Execution timed out 8084 ms 12620 KB Time limit exceeded
4 Incorrect 279 ms 12620 KB Unexpected end of file - int32 expected
5 Incorrect 301 ms 12620 KB Unexpected end of file - int32 expected
6 Incorrect 1804 ms 12620 KB Unexpected end of file - int32 expected
7 Incorrect 1574 ms 12620 KB Unexpected end of file - int32 expected
8 Incorrect 1432 ms 14668 KB Unexpected end of file - int32 expected
9 Incorrect 2557 ms 16248 KB Unexpected end of file - int32 expected
10 Incorrect 4517 ms 20016 KB Unexpected end of file - int32 expected
11 Incorrect 6461 ms 20016 KB Unexpected end of file - int32 expected
12 Incorrect 1928 ms 20016 KB Unexpected end of file - int32 expected
13 Incorrect 2595 ms 20016 KB Unexpected end of file - int32 expected
14 Incorrect 2917 ms 20016 KB Unexpected end of file - int32 expected
15 Incorrect 3985 ms 21376 KB Unexpected end of file - int32 expected
16 Incorrect 4061 ms 24652 KB Unexpected end of file - int32 expected
17 Execution timed out 6999 ms 24652 KB Time limit exceeded (wall clock)