oj.uz

Submission #1024523

# Submission time Handle Problem Language Result Execution time Memory
1024523 2024-07-16T06:56:23 Z Ice_man Regions (IOI09_regions) C++14
0 / 100
 1859 ms 131072 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

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


#define maxn 200005
#define maxr 20005
#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];
int ans[maxr][maxr];
int sz[maxn] , id[maxn];
int pre[maxn];
int timer;
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];
    }
}


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

    for(auto& nb : v[node])
        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)
            for(auto& e : c[i])
                if(used[e] == false)
                    dfs2(e , par[e] , 0 , color[e]);

    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() , id[e])
                        - lower_bound(tt[y].begin() , tt[y].end() , id[e] + sz[e] - 1);

        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:101:13: warning: unused variable 'x' [-Wunused-variable]
  101 |         int x;
      |             ^
regions.cpp:109:9: warning: unused variable 'sq' [-Wunused-variable]
  109 |     int sq = 500;
      |         ^~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 24152 KB Output isn't correct
2 Incorrect 4 ms 24152 KB Output isn't correct
3 Incorrect 5 ms 24152 KB Output isn't correct
4 Incorrect 6 ms 24152 KB Output isn't correct
5 Incorrect 8 ms 24316 KB Output isn't correct
6 Incorrect 12 ms 24152 KB Output isn't correct
7 Incorrect 17 ms 24152 KB Output isn't correct
8 Incorrect 25 ms 24408 KB Output isn't correct
9 Incorrect 20 ms 24664 KB Output isn't correct
10 Incorrect 57 ms 24660 KB Output isn't correct
11 Incorrect 93 ms 24920 KB Output isn't correct
12 Incorrect 94 ms 25432 KB Output isn't correct
13 Incorrect 130 ms 25432 KB Output isn't correct
14 Incorrect 205 ms 25688 KB Output isn't correct
15 Incorrect 189 ms 28760 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 76 ms 131072 KB Execution killed with signal 9
2 Runtime error 76 ms 131072 KB Execution killed with signal 9
3 Runtime error 72 ms 131072 KB Execution killed with signal 9
4 Incorrect 209 ms 25944 KB Output isn't correct
5 Incorrect 247 ms 27480 KB Output isn't correct
6 Incorrect 1075 ms 26968 KB Output isn't correct
7 Incorrect 1409 ms 27992 KB Output isn't correct
8 Incorrect 1004 ms 33112 KB Output isn't correct
9 Incorrect 1859 ms 32632 KB Output isn't correct
10 Runtime error 25 ms 28504 KB Execution killed with signal 11
11 Runtime error 32 ms 28504 KB Execution killed with signal 11
12 Runtime error 93 ms 131072 KB Execution killed with signal 9
13 Runtime error 93 ms 131072 KB Execution killed with signal 9
14 Runtime error 134 ms 131072 KB Execution killed with signal 9
15 Runtime error 25 ms 28504 KB Execution killed with signal 11
16 Runtime error 26 ms 28504 KB Execution killed with signal 11
17 Runtime error 92 ms 131072 KB Execution killed with signal 9