답안 #944386

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
944386 2024-03-12T16:25:31 Z FucKanh Regions (IOI09_regions) C++14
0 / 100
1754 ms 43100 KB
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>

using namespace std;

const int maxn = 2e5 + 2;
const int maxr = 25002;

int cnt[450][maxr], c[maxr], tin[maxn], tout[maxn], t, h[maxn], id[maxn], sz[maxr];
vector<int> a[maxn], in[maxn], out[maxn];

void dfs(int u, int pa = -1) {
    tin[u] = ++t;
    if (!c[h[u]]) c[h[u]] = u;
    for (int i = 0; i < a[u].size(); i++) {
        int v = a[u][i];
        if (v == pa) continue;
        dfs(v, u);
    }
//    cerr << "out " << u << " " << h[u] << " : " << c[h[u]] << endl;
    tout[u] = t;
    in[h[u]].push_back(tin[u]);
    out[h[u]].push_back(tout[u]);
}

void dfsc(int u, int check, int pa = -1) {
    if (h[u] == check && c[check] == 0) c[check] = u;
    for (int i = 0; i < a[u].size(); i++) {
        int v = a[u][i];
        if (v == pa) continue;
        dfsc(v, check, u);
    }
    if (c[check] == u) c[check] = 0;
    if (c[check]) cnt[id[check]][h[u]]++;
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n,r,q; cin >> n >> r >> q;
    cin >> h[1];
    for (int i = 2; i <= n; i++) {
        int x; cin >> x >> h[i];
        a[x].push_back(i);
        sz[h[i]]++;
    }
    for (int i = 1; i <= r; i++) {
        in[i].push_back(0);
        out[i].push_back(0);
    }
    dfs(1);

//    for (int i = 1; i <= r; i++) {
//        cerr << i << ": " << endl;
//        for (int j = 1; j < in[i].size(); j++) {
//            cerr << in[i][j] << " " << out[i][j] << endl;
//        }
//    }

    int dem = 0;
    for (int i = 1; i <= r; i++) {
        if (sz[i] >= 500) {
            id[i] = ++dem;
            c[i] = 0;
            dfsc(1, i);
//            cerr << i << ": " << endl;
//            for (int j = 1; j <= r; j++) {
//                cerr << cnt[dem][j] << " ";
//            } cerr << endl;
        }
    }
    cout << flush;
    for (int i =0; i < q; i++) {
        int r1, r2; cin >> r1 >> r2;
        if (sz[r1] >= 500) {
            cout << cnt[id[r1]][r2] << endl;
        }
        else {
            int pos = 1;
            int ans = 0;
//            cerr << r1 << ": ";
//            for (int i = 1; i < in[r1].size(); i++) {
//                cerr << in[r1][i] <<  " " << out[r1][i] << endl;
//            }
//            cerr << r2 << ": ";
//            for (int i = 1; i < in[r2].size(); i++) {
//                cerr << in[r2][i] <<  " " << out[r2][i] << endl;
//            }
            for (int i = 1; i < in[r1].size() && pos < in[r2].size(); i++) {
                while (pos < in[r2].size() && in[r2][pos] < in[r1][i]) pos++;
                while (pos < in[r2].size() && in[r2][pos] >= in[r1][i] && out[r2][pos] <= out[r1][i]) ans++, pos++;
            }
            cout << ans << endl;
        }
    }
    return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < a[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
regions.cpp: In function 'void dfsc(int, int, int)':
regions.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < a[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:89:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             for (int i = 1; i < in[r1].size() && pos < in[r2].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~
regions.cpp:89:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             for (int i = 1; i < in[r1].size() && pos < in[r2].size(); i++) {
      |                                                  ~~~~^~~~~~~~~~~~~~~
regions.cpp:90:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                 while (pos < in[r2].size() && in[r2][pos] < in[r1][i]) pos++;
      |                        ~~~~^~~~~~~~~~~~~~~
regions.cpp:91:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                 while (pos < in[r2].size() && in[r2][pos] >= in[r1][i] && out[r2][pos] <= out[r1][i]) ans++, pos++;
      |                        ~~~~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 16984 KB Output isn't correct
2 Incorrect 4 ms 16984 KB Output isn't correct
3 Incorrect 5 ms 16984 KB Output isn't correct
4 Incorrect 6 ms 16984 KB Output isn't correct
5 Incorrect 7 ms 16984 KB Output isn't correct
6 Incorrect 12 ms 17008 KB Output isn't correct
7 Incorrect 16 ms 16984 KB Output isn't correct
8 Incorrect 16 ms 16984 KB Output isn't correct
9 Incorrect 26 ms 17496 KB Output isn't correct
10 Incorrect 45 ms 17496 KB Output isn't correct
11 Incorrect 60 ms 17496 KB Output isn't correct
12 Incorrect 59 ms 18008 KB Output isn't correct
13 Incorrect 78 ms 17752 KB Output isn't correct
14 Incorrect 118 ms 18492 KB Output isn't correct
15 Incorrect 98 ms 21336 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 665 ms 21596 KB Output isn't correct
2 Incorrect 771 ms 22048 KB Output isn't correct
3 Incorrect 1131 ms 23912 KB Output isn't correct
4 Incorrect 116 ms 18580 KB Output isn't correct
5 Incorrect 178 ms 20568 KB Output isn't correct
6 Incorrect 415 ms 22276 KB Output isn't correct
7 Incorrect 592 ms 20764 KB Output isn't correct
8 Incorrect 620 ms 27480 KB Output isn't correct
9 Incorrect 880 ms 25956 KB Output isn't correct
10 Incorrect 1217 ms 31620 KB Output isn't correct
11 Incorrect 1489 ms 25396 KB Output isn't correct
12 Incorrect 814 ms 26816 KB Output isn't correct
13 Incorrect 1012 ms 27572 KB Output isn't correct
14 Incorrect 1344 ms 29912 KB Output isn't correct
15 Incorrect 1481 ms 33172 KB Output isn't correct
16 Incorrect 1754 ms 42144 KB Output isn't correct
17 Incorrect 1625 ms 43100 KB Output isn't correct