oj.uz

Submission #286390

# Submission time Handle Problem Language Result Execution time Memory
286390 2020-08-30T11:02:08 Z Kastanda Regions (IOI09_regions) C++11
100 / 100
 6711 ms 32660 KB 
/*
    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;
}

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 14 ms 9728 KB Output is correct
6 Correct 22 ms 9856 KB Output is correct
7 Correct 33 ms 9856 KB Output is correct
8 Correct 40 ms 9856 KB Output is correct
9 Correct 57 ms 10240 KB Output is correct
10 Correct 97 ms 10368 KB Output is correct
11 Correct 137 ms 10496 KB Output is correct
12 Correct 160 ms 10880 KB Output is correct
13 Correct 204 ms 10624 KB Output is correct
14 Correct 333 ms 11136 KB Output is correct
15 Correct 440 ms 13560 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2456 ms 14112 KB Output is correct
2 Correct 2655 ms 12800 KB Output is correct
3 Correct 4041 ms 15816 KB Output is correct
4 Correct 394 ms 11136 KB Output is correct
5 Correct 517 ms 12792 KB Output is correct
6 Correct 711 ms 14200 KB Output is correct
7 Correct 1511 ms 14328 KB Output is correct
8 Correct 1311 ms 22520 KB Output is correct
9 Correct 2987 ms 18040 KB Output is correct
10 Correct 3983 ms 32660 KB Output is correct
11 Correct 6711 ms 17404 KB Output is correct
12 Correct 2161 ms 19320 KB Output is correct
13 Correct 3076 ms 19448 KB Output is correct
14 Correct 3697 ms 20984 KB Output is correct
15 Correct 4654 ms 23416 KB Output is correct
16 Correct 4559 ms 28920 KB Output is correct
17 Correct 3820 ms 29504 KB Output is correct