oj.uz

답안 #1024522

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1024522 2024-07-16T06:55:55 Z Ice_man Regions (IOI09_regions) C++14
0 / 100
 116 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;
            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;
    }
}










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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3 ms 24152 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 24152 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 24152 KB Time limit exceeded (wall clock)
4 Execution timed out 4 ms 24152 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 24152 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 24152 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 24152 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 24408 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 24664 KB Time limit exceeded (wall clock)
10 Execution timed out 5 ms 24664 KB Time limit exceeded (wall clock)
11 Execution timed out 5 ms 24920 KB Time limit exceeded (wall clock)
12 Execution timed out 7 ms 25432 KB Time limit exceeded (wall clock)
13 Execution timed out 11 ms 25432 KB Time limit exceeded (wall clock)
14 Execution timed out 13 ms 25688 KB Time limit exceeded (wall clock)
15 Execution timed out 13 ms 28760 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 77 ms 131072 KB Execution killed with signal 9
2 Runtime error 71 ms 131072 KB Execution killed with signal 9
3 Runtime error 72 ms 131072 KB Execution killed with signal 9
4 Execution timed out 12 ms 25944 KB Time limit exceeded (wall clock)
5 Execution timed out 11 ms 27532 KB Time limit exceeded (wall clock)
6 Execution timed out 15 ms 26968 KB Time limit exceeded (wall clock)
7 Execution timed out 19 ms 27896 KB Time limit exceeded (wall clock)
8 Execution timed out 24 ms 33368 KB Time limit exceeded (wall clock)
9 Execution timed out 40 ms 32672 KB Time limit exceeded (wall clock)
10 Runtime error 28 ms 28504 KB Execution killed with signal 11
11 Runtime error 26 ms 28504 KB Execution killed with signal 11
12 Runtime error 116 ms 131072 KB Execution killed with signal 9
13 Runtime error 99 ms 131072 KB Execution killed with signal 9
14 Runtime error 103 ms 131072 KB Execution killed with signal 9
15 Runtime error 26 ms 28504 KB Execution killed with signal 11
16 Runtime error 26 ms 28504 KB Execution killed with signal 11
17 Runtime error 105 ms 131072 KB Execution killed with signal 9