oj.uz

Submission #870911

# Submission time Handle Problem Language Result Execution time Memory
870911 2023-11-09T12:54:56 Z aykhn Regions (IOI09_regions) C++17
55 / 100
 1647 ms 48424 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;
            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 11 ms 10584 KB Output is correct
7 Correct 13 ms 10840 KB Output is correct
8 Correct 18 ms 11092 KB Output is correct
9 Correct 22 ms 11352 KB Output is correct
10 Correct 46 ms 11864 KB Output is correct
11 Correct 69 ms 12352 KB Output is correct
12 Correct 77 ms 13168 KB Output is correct
13 Correct 88 ms 13800 KB Output is correct
14 Correct 118 ms 14976 KB Output is correct
15 Correct 133 ms 17700 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 601 ms 20244 KB Output isn't correct
2 Incorrect 664 ms 19904 KB Output isn't correct
3 Runtime error 64 ms 24612 KB Execution killed with signal 13
4 Correct 156 ms 14592 KB Output is correct
5 Correct 202 ms 15996 KB Output is correct
6 Correct 432 ms 16524 KB Output is correct
7 Correct 618 ms 18956 KB Output is correct
8 Correct 605 ms 26392 KB Output is correct
9 Correct 1024 ms 31892 KB Output is correct
10 Correct 1427 ms 35720 KB Output is correct
11 Correct 1647 ms 35720 KB Output is correct
12 Incorrect 707 ms 33316 KB Output isn't correct
13 Incorrect 904 ms 34776 KB Output isn't correct
14 Incorrect 1072 ms 36144 KB Output isn't correct
15 Incorrect 1392 ms 40632 KB Output isn't correct
16 Incorrect 1428 ms 48424 KB Output isn't correct
17 Incorrect 1464 ms 48300 KB Output isn't correct