제출 #286390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286390		Kastanda	Regions (IOI09_regions)	C++11	100 / 100	6711 ms	32660 KiB

regions

/*
    Take me to church
    I'll worship like a dog at the shrine of your lies
    I'll tell you my sins and you can sharpen your knife
    Offer me that deathless death
    Good God, let me give you my life
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 200005, K = 25004, SQ = 400, QS = N / SQ + 5;
int n, k, q, ts, tc, T[N], St[N], Fn[N], Id[K], R[QS][K];
vector < int > Adj[N], A[N];
void DFS(int v)
{
    St[v] = ts ++;
    A[T[v]].push_back(v);
    for (int u : Adj[v])
        DFS(u);
    Fn[v] = ts;
}
void DFS2(int v, int tp, int id, int cnt = 0)
{
    if (T[v] == tp)
        cnt ++;
    else
        R[id][T[v]] += cnt;
    for (int u : Adj[v])
        DFS2(u, tp, id, cnt);
}
inline bool CMP(int i, int j)
{
    return (St[i] < St[j]);
}
int main()
{
    scanf("%d%d%d%d", &n, &k, &q, &T[1]);
    for (int i = 2, p; i <= n; i ++)
        scanf("%d%d", &p, &T[i]), Adj[p].push_back(i);
    DFS(1);
    for (int i = 1; i <= k; i ++)
        if ((int)A[i].size() >= SQ)
            Id[i] = ++ tc, DFS2(1, i, tc);
    for (; q; q --)
    {
        int v, u;
        scanf("%d%d", &v, &u);
        if ((int)A[v].size() >= SQ)
        {
            printf("%d\n", R[Id[v]][u]);
            fflush(stdout);
            continue;
        }
        int tot = 0;
        for (int w : A[v])
            St[0] = Fn[w], tot += (int)(lower_bound(A[u].begin(), A[u].end(), 0, CMP) - lower_bound(A[u].begin(), A[u].end(), w, CMP));
        printf("%d\n", tot);
        fflush(stdout);
    }
    return 0;
}

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

regions.cpp: In function 'int main()':
regions.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |     scanf("%d%d%d%d", &n, &k, &q, &T[1]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |         scanf("%d%d", &p, &T[i]), Adj[p].push_back(i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |         scanf("%d%d", &v, &u);
      |         ~~~~~^~~~~~~~~~~~~~~~

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