oj.uz

Submission #1026955

# Submission time Handle Problem Language Result Execution time Memory
1026955 2024-07-18T15:04:27 Z Ice_man Regions (IOI09_regions) C++14
55 / 100
 3216 ms 61576 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>


#define maxn 200005
#define maxr 25005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

using namespace std;


typedef long long ll;
typedef pair <ll , ll> pll;
typedef pair <int , int> pii;
typedef long double ld;
typedef unsigned long long ull;




map <int , int> br[maxn];
int n , r , q;
vector <int> v[maxn];
int color[maxn];

vector <int> c[maxr];
map <int , int> ans[maxr];
int sz[maxn] , id[maxn];
int pre[maxn];
int timer;
int tout[maxn];

vector <int> tt[maxn];


void dfs(int node , int par)
{
    id[node] = timer;
    pre[timer] = color[node];

    sz[node] = 1;
    tt[color[node]].pb(timer);

    timer++;

    for(auto& nb : v[node])
    {
        if(nb == par)
            continue;

        dfs(nb , node);
        sz[node] += sz[nb];
    }
    tout[node] = timer;
}


bool used[maxn];
void dfs2(int node , int par , int br , int col)
{
    if(color[node] == col)
        used[node] = true;
    ans[col][color[node]] += br;

    for(auto& nb : v[node])
    {
        if(nb == par)
            continue;

        dfs2(nb , node , br + (col == color[node]) , col);
    }
}



int par[maxn];
void read()
{
    cin >> n >> r >> q;

    for(int i = 1; i <= n; i++)
    {
        if(i == 1)
        {
            cin >> color[i];
            c[color[i]].pb(i);
            continue;
        }

        int x;
        cin >> par[i] >> color[i];
        c[color[i]].pb(i);

        v[par[i]].pb(i);
        v[i].pb(par[i]);
    }

    int sq = 500;
    timer = 0;
    dfs(1 , 0);

    for(int i = 1; i <= r; i++)
        if(c[i].size() > 500)
                    dfs2(c[i][0] , par[c[i][0]] , 0 , color[c[i][0]]);

    int x , y;
    while(q--)
    {
        cin >> x >> y;
        if(c[x].size() > 500)
        {
            cout << ans[x][y] << endl;
            cout.flush();
            continue;
        }

        int curr = 0;
        for(auto& e : c[x])
            curr += (upper_bound(tt[y].begin() , tt[y].end() , tout[e] - 1) - tt[y].begin())
                        - (lower_bound(tt[y].begin() , tt[y].end() , id[e]) - tt[y].begin());

        cout << curr << endl;
        cout.flush();
    }
}










int main()
{

/**#ifdef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif*/

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ///startT = std::chrono::high_resolution_clock::now();

    read();


    return 0;
}

Compilation message

regions.cpp: In function 'void read()':
regions.cpp:109:13: warning: unused variable 'x' [-Wunused-variable]
  109 |         int x;
      |             ^
regions.cpp:117:9: warning: unused variable 'sq' [-Wunused-variable]
  117 |     int sq = 500;
      |         ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25688 KB Output is correct
2 Correct 4 ms 25688 KB Output is correct
3 Correct 5 ms 25688 KB Output is correct
4 Correct 5 ms 25688 KB Output is correct
5 Correct 7 ms 25636 KB Output is correct
6 Correct 12 ms 25688 KB Output is correct
7 Correct 20 ms 25688 KB Output is correct
8 Correct 15 ms 25688 KB Output is correct
9 Correct 39 ms 26196 KB Output is correct
10 Correct 51 ms 26196 KB Output is correct
11 Correct 90 ms 26456 KB Output is correct
12 Correct 100 ms 26968 KB Output is correct
13 Correct 124 ms 26712 KB Output is correct
14 Correct 207 ms 27224 KB Output is correct
15 Correct 174 ms 30040 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1483 ms 30296 KB Output isn't correct
2 Incorrect 1694 ms 30092 KB Output isn't correct
3 Incorrect 2167 ms 32848 KB Output isn't correct
4 Correct 172 ms 27224 KB Output is correct
5 Correct 261 ms 29016 KB Output is correct
6 Correct 1073 ms 28504 KB Output is correct
7 Correct 1265 ms 29528 KB Output is correct
8 Correct 965 ms 34648 KB Output is correct
9 Correct 1761 ms 34124 KB Output is correct
10 Correct 3197 ms 39504 KB Output is correct
11 Correct 3216 ms 35852 KB Output is correct
12 Incorrect 1070 ms 36112 KB Output isn't correct
13 Incorrect 1512 ms 37352 KB Output isn't correct
14 Incorrect 1648 ms 39356 KB Output isn't correct
15 Incorrect 2447 ms 44592 KB Output isn't correct
16 Incorrect 2372 ms 55164 KB Output isn't correct
17 Incorrect 2309 ms 61576 KB Output isn't correct