oj.uz

답안 #817647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817647 2023-08-09T14:26:34 Z hariaakas646 Regions (IOI09_regions) C++17
45 / 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 = 200;
    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);
      |         ^~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 17 ms 336 KB Output is correct
7 Correct 26 ms 336 KB Output is correct
8 Correct 30 ms 464 KB Output is correct
9 Correct 20 ms 976 KB Output is correct
10 Correct 46 ms 1104 KB Output is correct
11 Correct 107 ms 1488 KB Output is correct
12 Correct 107 ms 2188 KB Output is correct
13 Correct 150 ms 2256 KB Output is correct
14 Correct 233 ms 2832 KB Output is correct
15 Correct 245 ms 5832 KB Output is correct

Subtask #2
30.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6318 ms 65148 KB Output is correct
2 Correct 1957 ms 109044 KB Output is correct
3 Execution timed out 8038 ms 16216 KB Time limit exceeded
4 Correct 257 ms 3280 KB Output is correct
5 Correct 287 ms 4952 KB Output is correct
6 Correct 2117 ms 29764 KB Output is correct
7 Correct 1700 ms 34596 KB Output is correct
8 Execution timed out 8015 ms 63332 KB Time limit exceeded
9 Runtime error 7149 ms 131072 KB Execution killed with signal 9
10 Execution timed out 8050 ms 116516 KB Time limit exceeded
11 Runtime error 1489 ms 131072 KB Execution killed with signal 9
12 Runtime error 4216 ms 131072 KB Execution killed with signal 9
13 Runtime error 6890 ms 131072 KB Execution killed with signal 9
14 Execution timed out 8082 ms 26388 KB Time limit exceeded
15 Execution timed out 8054 ms 21924 KB Time limit exceeded
16 Execution timed out 8026 ms 71224 KB Time limit exceeded
17 Execution timed out 8039 ms 29072 KB Time limit exceeded