제출 #409257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409257		ivycube	Regions (IOI09_regions)	C++14	0 / 100	70 ms	13248 KiB

regions

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>

using namespace std;
using PII = pair<int, int>;

const int N = 200005, R = 25005, UP = 450 /*threshold*/;

int n, m, k, region[N], sz[R], ans[N], cnt[R];;
map<PII, int> qtoi;
vector<int> adj[N];
vector<PII> lookdown[R], lookup[R];

void dfs1(int u) {
    int r1 = region[u];
    for (auto p : lookdown[r1]) {
        int qid = p.second, r2 = p.first;
        ans[qid] -= cnt[r2];
    }
    cnt[r1] ++ ;
    for (auto v : adj[u]) dfs1(v);
    for (auto p : lookdown[r1]) {
        int qid = p.second, r2 = p.first;
        ans[qid] += cnt[r2];
    }
}

void dfs2(int u) {
    int r2 = region[u];
    cnt[r2] ++ ;
    for (auto p : lookup[r2]) {
        int qid = p.second, r1 = p.first;
        ans[qid] += cnt[r1];
    }
    for (auto v : adj[u]) dfs2(v);
    cnt[r2] -- ;
}

int main() {
    scanf("%d%d%d", &n, &k, &m);
    scanf("%d", &region[1]);
    sz[region[1]] ++ ;
    
    int j, r;
    for (int i = 2; i <= n; i++) {
        scanf("%d%d", &j, &r);
        adj[j].push_back(i);
        region[i] = r;
        sz[r] ++ ;
    }
    
    int a, b;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &a, &b);
        if (qtoi[{a, b}]) {
            ans[i] = -qtoi[{a, b}];
            continue;
        }
        qtoi[{a, b}] = i;
        
        if (sz[b] >= UP) lookdown[a].push_back({b, i});
        else lookup[b].push_back({a, i});
    }
    
    dfs1(1);
    memset(cnt, 0, sizeof cnt);
    dfs2(1);
    
    for (int i = 1; i <= m; i++) {
        if (ans[i] < 0) ans[i] = ans[-ans[i]];
        printf("%d\n", ans[i]);
    }
    
    return 0;
}

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

regions.cpp: In function 'int main()':
regions.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d%d%d", &n, &k, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d", &region[1]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%d%d", &j, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

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