답안 #817625

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817625 2023-08-09T14:10:38 Z hariaakas646 Regions (IOI09_regions) C++17
15 / 100
8000 ms 131072 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(n+1);
            for(auto e : reg[i])
            dfs(e, par[e], out);
            prec[i] = out;
        }
    }
    st = en = vi(n + 1);
    vvi pos(r + 1);
    euler(1, 0);
    forr(i, 1, r + 1)
    {
        for (auto e : reg[i])
        {
            pos[i].pb(st[e]);
        }
        sort(all(pos[i]));
        // printf("%d\n", i);
        // for(auto e : pos[i]) printf("%d  ", e);
        // printf("\n");
    }
    
    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[e]) - lower_bound(all(pos[b]), st[e]);
                // printf("%d %d %lld\n", st[e], en[e], tot);
            }
            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:117:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |         if (reg[a].size() < x)
      |             ~~~~~~~~~~~~~~^~~
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:115:9: note: in expansion of macro 'scd'
  115 |         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:116:9: note: in expansion of macro 'scd'
  116 |         scd(b);
      |         ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 7 ms 464 KB Output is correct
6 Correct 20 ms 1872 KB Output is correct
7 Correct 27 ms 2128 KB Output is correct
8 Correct 24 ms 3612 KB Output is correct
9 Correct 127 ms 12572 KB Output is correct
10 Correct 86 ms 34008 KB Output is correct
11 Correct 180 ms 33188 KB Output is correct
12 Correct 610 ms 72604 KB Output is correct
13 Correct 107 ms 66180 KB Output is correct
14 Correct 225 ms 49692 KB Output is correct
15 Correct 5850 ms 80612 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8026 ms 122720 KB Time limit exceeded
2 Runtime error 847 ms 131072 KB Execution killed with signal 9
3 Runtime error 4869 ms 131072 KB Execution killed with signal 9
4 Runtime error 133 ms 131072 KB Execution killed with signal 9
5 Runtime error 259 ms 131072 KB Execution killed with signal 9
6 Runtime error 130 ms 131072 KB Execution killed with signal 9
7 Runtime error 164 ms 131072 KB Execution killed with signal 9
8 Runtime error 425 ms 131072 KB Execution killed with signal 9
9 Runtime error 297 ms 131072 KB Execution killed with signal 9
10 Runtime error 139 ms 131072 KB Execution killed with signal 9
11 Runtime error 123 ms 131072 KB Execution killed with signal 9
12 Runtime error 197 ms 131072 KB Execution killed with signal 9
13 Runtime error 267 ms 131072 KB Execution killed with signal 9
14 Runtime error 197 ms 131072 KB Execution killed with signal 9
15 Runtime error 465 ms 131072 KB Execution killed with signal 9
16 Runtime error 683 ms 131072 KB Execution killed with signal 9
17 Runtime error 376 ms 131072 KB Execution killed with signal 9