oj.uz

Submission #870912

# Submission time Handle Problem Language Result Execution time Memory
870912 2023-11-09T12:56:25 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1581 ms 53620 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 = 600;

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;
            continue;
        }
        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:109: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]
  109 |         while (i < v1[u].size() && j < v2[v].size())
      |                ~~^~~~~~~~~~~~~~
regions.cpp:109: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]
  109 |         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 5 ms 10584 KB Output is correct
6 Correct 13 ms 10840 KB Output is correct
7 Correct 15 ms 10840 KB Output is correct
8 Correct 21 ms 10840 KB Output is correct
9 Correct 29 ms 11352 KB Output is correct
10 Correct 48 ms 11864 KB Output is correct
11 Correct 66 ms 12220 KB Output is correct
12 Correct 80 ms 13156 KB Output is correct
13 Correct 93 ms 13756 KB Output is correct
14 Correct 117 ms 14852 KB Output is correct
15 Correct 152 ms 17696 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 60 ms 20248 KB Execution killed with signal 13
2 Runtime error 80 ms 19912 KB Execution killed with signal 13
3 Runtime error 73 ms 24620 KB Execution killed with signal 13
4 Correct 153 ms 14596 KB Output is correct
5 Correct 214 ms 15972 KB Output is correct
6 Correct 435 ms 16660 KB Output is correct
7 Correct 650 ms 19040 KB Output is correct
8 Correct 638 ms 26388 KB Output is correct
9 Correct 986 ms 31708 KB Output is correct
10 Correct 1372 ms 35640 KB Output is correct
11 Correct 1581 ms 35724 KB Output is correct
12 Incorrect 697 ms 33328 KB Output isn't correct
13 Incorrect 882 ms 34776 KB Output isn't correct
14 Runtime error 419 ms 41144 KB Execution killed with signal 13
15 Incorrect 1381 ms 40592 KB Output isn't correct
16 Incorrect 1465 ms 48420 KB Output isn't correct
17 Runtime error 268 ms 53620 KB Execution killed with signal 13