oj.uz

Submission #881690

# Submission time Handle Problem Language Result Execution time Memory
881690 2023-12-01T18:05:25 Z sheldon Regions (IOI09_regions) C++14
0 / 100
 64 ms 30792 KB 
#include <bits/stdc++.h>

using namespace std;

const int nax = 2e5 + 5;

int region[nax];
vector<int> edges[nax], positions[nax];
int tin[nax], tout[nax], who[nax];
int timer = 0;
unordered_map<int, int> mp[25005];

void dfs (int u, int p) {
    tin[u] = ++timer;
    who[timer] = u;
    positions[region[u]].push_back(timer);
    for (int v : edges[u]) {
        if (v != p) {
            dfs (v, u);
        }
    }
    tout[u] = timer;
}

void solve() {
    int n, r, q;
    cin >> n >> r >> q;
    cin >> region[1];
    for (int i = 2; i <= n; ++i) {
        int p;
        cin >> p >> region[i];
        edges[i].push_back(p);
        edges[p].push_back(i);
    }
    dfs (1, 0);
    const int B = sqrt(n) + 5;
    // for (int reg = 1; reg <= r; ++reg) {
    //     if (positions[reg].size() >= B) {
    //         vector<int> pref(n + 2);
    //         for (int i = 1; i <= n; ++i) {
    //             if (region[who[i]] == reg) {
    //                 pref[i + 1]++;
    //                 pref[tout[who[i]] + 1]--;
    //             }
    //         }
    //         for (int i = 1; i <= n; ++i) {
    //             pref[i] += pref[i - 1];
    //             mp[reg][region[who[i]]] += pref[i];
    //         }
    //     }
    // }
    // while (q--) {

    //     int reg1, reg2;
    //     cin >> reg1 >> reg2;
    //     if (positions[reg1].size() >= B) {
    //         cout << mp[reg1][reg2] << endl;
    //     } else {
    //         int ans = 0;
    //         for (int i : positions[reg1]) {
    //             if (region[who[i]] == reg1) {
    //                 auto it1 = upper_bound(positions[reg2].begin(), positions[reg2].end(), tout[who[i]]) - positions[reg2].begin();
    //                 auto it2 = lower_bound(positions[reg2].begin(), positions[reg2].end(), i) - positions[reg2].begin();
    //                 if (it1 != 0) {
    //                     ans += (int) it1 - it2;
    //                 }
    //             }
    //         }
    //         cout << ans << endl;
    //     }
    // }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:36:15: warning: unused variable 'B' [-Wunused-variable]
   36 |     const int B = sqrt(n) + 5;
      |               ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 13400 KB Unexpected end of file - int32 expected
2 Incorrect 3 ms 13400 KB Unexpected end of file - int32 expected
3 Incorrect 3 ms 13400 KB Unexpected end of file - int32 expected
4 Incorrect 3 ms 13400 KB Unexpected end of file - int32 expected
5 Incorrect 3 ms 13400 KB Unexpected end of file - int32 expected
6 Incorrect 3 ms 13400 KB Unexpected end of file - int32 expected
7 Incorrect 3 ms 13536 KB Unexpected end of file - int32 expected
8 Incorrect 3 ms 13656 KB Unexpected end of file - int32 expected
9 Incorrect 4 ms 13912 KB Unexpected end of file - int32 expected
10 Incorrect 7 ms 13912 KB Unexpected end of file - int32 expected
11 Incorrect 6 ms 14168 KB Unexpected end of file - int32 expected
12 Incorrect 7 ms 14556 KB Unexpected end of file - int32 expected
13 Incorrect 8 ms 14424 KB Unexpected end of file - int32 expected
14 Incorrect 11 ms 14780 KB Unexpected end of file - int32 expected
15 Incorrect 11 ms 16984 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 17156 KB Unexpected end of file - int32 expected
2 Incorrect 22 ms 16884 KB Unexpected end of file - int32 expected
3 Incorrect 22 ms 18728 KB Unexpected end of file - int32 expected
4 Incorrect 10 ms 14860 KB Unexpected end of file - int32 expected
5 Incorrect 12 ms 16288 KB Unexpected end of file - int32 expected
6 Incorrect 16 ms 15960 KB Unexpected end of file - int32 expected
7 Incorrect 26 ms 16960 KB Unexpected end of file - int32 expected
8 Incorrect 26 ms 20956 KB Unexpected end of file - int32 expected
9 Incorrect 48 ms 20932 KB Unexpected end of file - int32 expected
10 Incorrect 44 ms 25132 KB Unexpected end of file - int32 expected
11 Incorrect 60 ms 22656 KB Unexpected end of file - int32 expected
12 Incorrect 62 ms 21536 KB Unexpected end of file - int32 expected
13 Incorrect 61 ms 22488 KB Unexpected end of file - int32 expected
14 Incorrect 64 ms 22364 KB Unexpected end of file - int32 expected
15 Incorrect 57 ms 25504 KB Unexpected end of file - int32 expected
16 Incorrect 54 ms 30792 KB Unexpected end of file - int32 expected
17 Incorrect 52 ms 29772 KB Unexpected end of file - int32 expected