oj.uz

Submission #870910

# Submission time Handle Problem Language Result Execution time Memory
870910 2023-11-09T12:53:15 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1580 ms 48696 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);
        adj[i].pb(p[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:108: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]
  108 |         while (i < v1[u].size() && j < v2[v].size())
      |                ~~^~~~~~~~~~~~~~
regions.cpp:108: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]
  108 |         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 4 ms 10584 KB Output is correct
5 Correct 5 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 19 ms 10840 KB Output is correct
9 Correct 28 ms 11412 KB Output is correct
10 Correct 52 ms 12116 KB Output is correct
11 Correct 58 ms 12376 KB Output is correct
12 Correct 81 ms 13048 KB Output is correct
13 Correct 95 ms 13884 KB Output is correct
14 Correct 117 ms 14844 KB Output is correct
15 Correct 133 ms 17704 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 396 ms 20504 KB Execution killed with signal 13
2 Runtime error 463 ms 20168 KB Execution killed with signal 13
3 Runtime error 64 ms 24604 KB Execution killed with signal 13
4 Correct 139 ms 14588 KB Output is correct
5 Correct 215 ms 15980 KB Output is correct
6 Correct 480 ms 16532 KB Output is correct
7 Correct 619 ms 18952 KB Output is correct
8 Correct 610 ms 26396 KB Output is correct
9 Correct 989 ms 31776 KB Output is correct
10 Correct 1396 ms 35668 KB Output is correct
11 Correct 1580 ms 35728 KB Output is correct
12 Runtime error 583 ms 33352 KB Execution killed with signal 13
13 Runtime error 713 ms 34832 KB Execution killed with signal 13
14 Runtime error 821 ms 36196 KB Execution killed with signal 13
15 Execution timed out 756 ms 40648 KB Time limit exceeded (wall clock)
16 Execution timed out 653 ms 48696 KB Time limit exceeded (wall clock)
17 Execution timed out 663 ms 48600 KB Time limit exceeded (wall clock)