oj.uz

Submission #817591

# Submission time Handle Problem Language Result Execution time Memory
817591 2023-08-09T13:49:34 Z hariaakas646 Regions (IOI09_regions) C++17
0 / 100
 101 ms 31880 KB 
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;

vvi reg, graph;
vi regi;
vi st, en;
int timer = 0;

void dfs(int x, int par, vll &vec)
{
    vec[regi[x]]++;
    for (auto e : graph[x])
    {
        if (e != par)
        {
            dfs(e, x, vec);
        }
    }
}

void euler(int x, int par)
{
    st[x] = ++timer;
    for (auto e : graph[x])
    {
        if (e != par)
        {
            euler(e, x);
        }
    }
    en[x] = timer;
}

int main()
{
    int n, r, q;
    scd(n);
    scd(r);
    scd(q);
    int x = 1000;
    reg = vvi(r + 1);
    regi = vi(n + 1);
    int h;
    scd(h);
    reg[h].pb(1);
    regi[1] = h;
    graph = vvi(n + 1);
    vi par(n + 1);

    forr(i, 2, n + 1)
    {
        int p, h;
        scd(p);
        scd(h);
        reg[h].pb(i);
        graph[i].pb(p);
        graph[p].pb(i);
        regi[i] = h;
        par[i] = p;
    }

    vector<vll> prec(r + 1);

    forr(i, 1, r + 1)
    {
        if (reg[i].size() < x)
        {
            vll out;
            dfs(i, par[i], out);
            prec[i] = out;
        }
    }
    st = en = vi(n + 1);
    vvi pos(r + 1);
    forr(i, 1, r + 1)
    {
        for (auto e : reg[i])
        {
            pos[i].pb(st[e]);
        }
        sort(all(pos[i]));
    }
    euler(1, 0);
    frange(_, q)
    {
        int a, b;
        scd(a);
        scd(b);
        if (reg[a].size() < x)
        {
            printf("%lld\n", prec[a][b]);
            fflush(stdout);
        }
        else
        {
            lli tot = 0;
            for (auto e : reg[a])
            {
                tot += upper_bound(all(pos[b]), en[a]) - lower_bound(all(pos[b]), st[a]);
            }
            printf("%lld\n", tot);
            fflush(stdout);
        }
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:89:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         if (reg[i].size() < x)
      |             ~~~~~~~~~~~~~~^~~
regions.cpp:112:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |         if (reg[a].size() < x)
      |             ~~~~~~~~~~~~~~^~~
regions.cpp:120:23: warning: unused variable 'e' [-Wunused-variable]
  120 |             for (auto e : reg[a])
      |                       ^
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
regions.cpp:60:5: note: in expansion of macro 'scd'
   60 |     scd(n);
      |     ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
regions.cpp:61:5: note: in expansion of macro 'scd'
   61 |     scd(r);
      |     ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
regions.cpp:62:5: note: in expansion of macro 'scd'
   62 |     scd(q);
      |     ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
regions.cpp:67:5: note: in expansion of macro 'scd'
   67 |     scd(h);
      |     ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
regions.cpp:76:9: note: in expansion of macro 'scd'
   76 |         scd(p);
      |         ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
regions.cpp:77:9: note: in expansion of macro 'scd'
   77 |         scd(h);
      |         ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
regions.cpp:110:9: note: in expansion of macro 'scd'
  110 |         scd(a);
      |         ^~~
regions.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
regions.cpp:111:9: note: in expansion of macro 'scd'
  111 |         scd(b);
      |         ^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 336 KB Execution killed with signal 11
2 Runtime error 1 ms 336 KB Execution killed with signal 11
3 Runtime error 0 ms 336 KB Execution killed with signal 11
4 Runtime error 1 ms 336 KB Execution killed with signal 11
5 Runtime error 1 ms 464 KB Execution killed with signal 11
6 Runtime error 1 ms 464 KB Execution killed with signal 11
7 Runtime error 2 ms 592 KB Execution killed with signal 11
8 Runtime error 2 ms 720 KB Execution killed with signal 11
9 Runtime error 3 ms 1104 KB Execution killed with signal 11
10 Runtime error 4 ms 1872 KB Execution killed with signal 11
11 Runtime error 6 ms 2440 KB Execution killed with signal 11
12 Runtime error 10 ms 3248 KB Execution killed with signal 11
13 Runtime error 8 ms 3860 KB Execution killed with signal 11
14 Runtime error 10 ms 4688 KB Execution killed with signal 11
15 Runtime error 16 ms 6096 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 10660 KB Execution killed with signal 11
2 Runtime error 24 ms 11660 KB Execution killed with signal 11
3 Runtime error 27 ms 12740 KB Execution killed with signal 11
4 Runtime error 10 ms 5096 KB Execution killed with signal 11
5 Runtime error 12 ms 6084 KB Execution killed with signal 11
6 Runtime error 21 ms 8332 KB Execution killed with signal 11
7 Runtime error 24 ms 11336 KB Execution killed with signal 11
8 Runtime error 39 ms 15460 KB Execution killed with signal 11
9 Runtime error 55 ms 23344 KB Execution killed with signal 11
10 Runtime error 67 ms 27352 KB Execution killed with signal 11
11 Runtime error 92 ms 31880 KB Execution killed with signal 11
12 Runtime error 70 ms 28452 KB Execution killed with signal 11
13 Runtime error 101 ms 28524 KB Execution killed with signal 11
14 Runtime error 91 ms 30604 KB Execution killed with signal 11
15 Runtime error 73 ms 31308 KB Execution killed with signal 11
16 Runtime error 67 ms 31048 KB Execution killed with signal 11
17 Runtime error 81 ms 30560 KB Execution killed with signal 11