oj.uz

Submission #870908

# Submission time Handle Problem Language Result Execution time Memory
870908 2023-11-09T12:49:34 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1580 ms 48732 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[id[cur]][reg[a]] = mp[id[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[id[cur]][reg[a]]= mp[id[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 = 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 2 ms 10584 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 3 ms 10584 KB Output is correct
5 Correct 6 ms 10584 KB Output is correct
6 Correct 11 ms 10584 KB Output is correct
7 Correct 14 ms 11092 KB Output is correct
8 Correct 15 ms 10840 KB Output is correct
9 Correct 23 ms 11352 KB Output is correct
10 Correct 44 ms 11608 KB Output is correct
11 Correct 64 ms 12324 KB Output is correct
12 Correct 77 ms 13224 KB Output is correct
13 Correct 94 ms 13336 KB Output is correct
14 Correct 121 ms 14668 KB Output is correct
15 Correct 138 ms 17704 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 20096 KB Execution killed with signal 13
2 Runtime error 55 ms 18708 KB Execution killed with signal 13
3 Runtime error 63 ms 24592 KB Execution killed with signal 13
4 Correct 148 ms 14336 KB Output is correct
5 Correct 201 ms 15980 KB Output is correct
6 Correct 443 ms 16108 KB Output is correct
7 Correct 646 ms 18484 KB Output is correct
8 Correct 594 ms 26380 KB Output is correct
9 Correct 995 ms 31236 KB Output is correct
10 Correct 1403 ms 35612 KB Output is correct
11 Correct 1580 ms 32388 KB Output is correct
12 Runtime error 496 ms 33484 KB Execution killed with signal 13
13 Execution timed out 501 ms 34008 KB Time limit exceeded (wall clock)
14 Execution timed out 704 ms 34976 KB Time limit exceeded (wall clock)
15 Execution timed out 564 ms 41116 KB Time limit exceeded (wall clock)
16 Execution timed out 459 ms 48732 KB Time limit exceeded (wall clock)
17 Runtime error 150 ms 48312 KB Execution killed with signal 13