제출 #765309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765309		keta_tsimakuridze	Regions (IOI09_regions)	C++14	40 / 100	933 ms	131072 KiB

regions

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, M = 25e3 + 5, mod = 1e9 + 7, B = 2000; // !
int t, a[N], id[M], cur, cnt[M], CN2[105][M], CN1[M][105], dp[N][105], timer;
vector<pair<int,int>> reg[M];
vector<int> V[N];
void dfs(int u) {
    ++timer;
    reg[a[u]].push_back({timer, 1});
    ++cnt[id[a[u]]];
    for(int j = 1; j <= cur; j++) {
        CN2[j][u] += cnt[j];
    }
    for(int i = 0; i < V[u].size(); i++) {
        int v = V[u][i];
        dfs(v);
        for(int j = 1; j <= cur; j++) {
            dp[u][j] += dp[v][j];
        }
    }
    --cnt[id[a[u]]];
    ++dp[u][id[a[u]]];
    for(int j = 1; j <= cur; j++) {
        CN1[u][j] += dp[u][j];
    }
    reg[a[u]].push_back({timer + 1, 0});
}
main(){
    int n, r, q;
    cin >> n >> r >> q;
    for(int i = 1; i <= n; i++) {
        if(i >= 2) {
            int k; cin >> k;
            V[k].push_back(i);
        }
        cin >> a[i];
        ++cnt[a[i]];
    }
//    cout << "+" << endl;
    cur = 0;
    for(int i = 1; i <= r; i++) {
        if(cnt[i] >= B) {
            id[i] = ++cur;
//            val[cur] = i;
        }
        cnt[i] = 0;
    }
    dfs(1);
    while(q--) {
        int u, v;
        cin >> u >> v;
        if(id[u]) {
            cout << CN2[id[u]][v] << endl;
        } else if(id[v]) {
            cout << CN2[u][id[v]] << endl;
        } else {
            int l = -1;
            int cn = 0, ans = 0;
            for(int i = 0; i < reg[u].size(); i++) {
                while(l + 1 < (int)reg[v].size() && reg[v][l + 1].f < reg[u][i].f) {
                    ++l;
                    cn += reg[v][l].s;
                }
                ans += cn * (reg[u][i].s ? -1 : 1);
            }
            cout << ans << endl;
        }
    }
 }

컴파일 시 표준 에러 (stderr) 메시지

regions.cpp: In function 'void dfs(long long int)':
regions.cpp:18:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:63:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for(int i = 0; i < reg[u].size(); i++) {
      |                            ~~^~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 25 / 85