제출 #765337

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

regions

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, M = 25e3 + 5, mod = 1e9 + 7, B = 400; // !
int t, a[N], timer, id[M], cur, cnt[M], CN[M], in[N], out[N];
ll CN2[505][M];
vector<int> reg[M];
vector<int> V[N];
set<pii> s[N];
void dfs2(int u) {
    in[u] = ++timer;
    ++cnt[id[a[u]]];
    s[a[u]].insert({in[u], (int)s[a[u]].size()});
    reg[a[u]].push_back(u);
    for(int j = 1; j <= cur; j++) {
        CN2[j][a[u]] += cnt[j];
    }
    for(int i = 0; i < V[u].size(); i++) dfs2(V[u][i]);
    --cnt[id[a[u]]];
    out[u] = timer;
}
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]];
    }
    cur = 0;
    for(int i = 1; i <= r; i++) {
        if(cnt[i] >= B) {
            id[i] = ++cur;
        }
        cnt[i] = 0;
    }
    for(int i = 1; i <= r; i++) cnt[i] = 0, s[i].insert({0, 0});
    dfs2(1);
    while(q--) {
        int u, v;
        cin >> u >> v;
        if(id[u]) {
            cout << CN2[id[u]][v] << endl;
        } else {
            ll ans = 0;
            for(int j = 0; j < reg[u].size(); j++) {
                ans += (*--s[v].upper_bound({out[reg[u][j]] + 1, 0})).s - (*--s[v].upper_bound({in[reg[u][j]], 0})).s;
            }
            cout << ans << endl;
        }
    }
 }

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

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

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