oj.uz

Submission #870909

# Submission time Handle Problem Language Result Execution time Memory
870909 2023-11-09T12:51:14 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1590 ms 48472 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define pb push_back
#define pii pair<int, int>
#define mpr make_pair
#define fi first
#define se second
#define int ll
#define all(v) v.begin(), v.end()

const int MXN = 2e5 + 5;
const int MXR = 25e3 + 5;
const int B = 2000;

int n, r, q;
int reg[MXN], p[MXN];
vector<int> idx[MXR];
vector<pii> v1[MXR];
vector<int> v2[MXR];
vector<int> adj[MXN];
int id[MXR], dp[MXN], in[MXN], out[MXN];
vector<vector<int>> mp, mp1;
int tim = -1;
int cur = -1;

void dfs(int a, int p)
{
    in[a] = ++tim;
    for (int v : adj[a])
    {
        if (v == p) continue;
        dfs(v, a);
    }
    out[a] = tim;
}

void dfs1(int a, int p, int seen)
{
    if (reg[a] != cur) mp[cur][reg[a]] = mp[cur][reg[a]] + seen;
    for (int v : adj[a])
    {
        if (v == p) continue;
        dfs1(v, a, seen + (reg[a] == cur));
        dp[a] += dp[v];
    }
    dp[a] += (reg[a] == cur);
    if (cur != reg[a] && idx[reg[a]].size() < B) mp1[cur][reg[a]]= mp[cur][reg[a]] + dp[a];
}

signed main()
{
    cin >> n >> r >> q;
    cin >> reg[1];
    idx[reg[1]].pb(1);
    for (int i = 2; i <= n; i++)
    {
        cin >> p[i] >> reg[i];
        adj[p[i]].pb(i);
        idx[reg[i]].pb(i);
    }
    dfs(1, 1);
    for (int i = 1; i <= r; i++)
    {
        for (int x : idx[i])
        {
            v1[i].pb(mpr(in[x], 1));
            v1[i].pb(mpr(out[x] + 1, -1));
            v2[i].pb(in[x]);
        }
        sort(all(v1[i]));
        sort(all(v2[i]));
    }
    int cnt = 0;
    for (int i = 1; i <= r; i++)
    {
        if (idx[i].size() < B) continue; 
        id[i] = cnt++;
    }
    mp.resize(cnt + 1, vector<int> (r + 1, 0));
    mp1.resize(cnt + 1, vector<int> (r + 1, 0));
    for (int i = 1; i <= r; i++)
    {
        if (idx[i].size() < B) continue; 
        cur = id[i];
        dfs1(1, 1, 0);
    }
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        if (idx[u].size() >= B)
        {
            cout << mp[id[u]][v] << endl;
            continue;
        }
        if (idx[v].size() >= B)
        {
            cout << mp1[id[v]][u] << endl;
        }
        int i = 0;
        int j = 0;
        ll ans = 0;
        int rn = 0;
        while (i < v1[u].size() && j < v2[v].size())
        {
            if (v1[u][i].fi <= v2[v][j]) rn += v1[u][i++].se;
            else 
            {
                ans = ans + rn;
                j++;
            }
        }
        cout << ans << endl;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:107:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         while (i < v1[u].size() && j < v2[v].size())
      |                ~~^~~~~~~~~~~~~~
regions.cpp:107:38: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         while (i < v1[u].size() && j < v2[v].size())
      |                                    ~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 3 ms 10584 KB Output is correct
3 Correct 3 ms 10584 KB Output is correct
4 Correct 4 ms 10584 KB Output is correct
5 Correct 4 ms 10584 KB Output is correct
6 Correct 11 ms 10584 KB Output is correct
7 Correct 15 ms 10840 KB Output is correct
8 Correct 17 ms 10840 KB Output is correct
9 Correct 24 ms 11352 KB Output is correct
10 Correct 45 ms 11608 KB Output is correct
11 Correct 62 ms 12376 KB Output is correct
12 Correct 82 ms 13104 KB Output is correct
13 Correct 96 ms 13372 KB Output is correct
14 Correct 112 ms 14668 KB Output is correct
15 Correct 133 ms 17696 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 379 ms 20108 KB Execution killed with signal 13
2 Runtime error 412 ms 18728 KB Execution killed with signal 13
3 Runtime error 64 ms 24588 KB Execution killed with signal 13
4 Correct 151 ms 14332 KB Output is correct
5 Correct 209 ms 15972 KB Output is correct
6 Correct 465 ms 16112 KB Output is correct
7 Correct 622 ms 18476 KB Output is correct
8 Correct 614 ms 26384 KB Output is correct
9 Correct 1006 ms 31232 KB Output is correct
10 Correct 1396 ms 35616 KB Output is correct
11 Correct 1590 ms 32388 KB Output is correct
12 Runtime error 503 ms 33472 KB Execution killed with signal 13
13 Runtime error 588 ms 34252 KB Execution killed with signal 13
14 Runtime error 705 ms 34964 KB Execution killed with signal 13
15 Execution timed out 680 ms 40640 KB Time limit exceeded (wall clock)
16 Execution timed out 557 ms 48472 KB Time limit exceeded (wall clock)
17 Execution timed out 579 ms 48364 KB Time limit exceeded (wall clock)