oj.uz

답안 #817649

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817649 2023-08-09T14:27:28 Z hariaakas646 Regions (IOI09_regions) C++17
65 / 100
 8000 ms 77528 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 = 400;
    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 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 12 ms 336 KB Output is correct
7 Correct 21 ms 384 KB Output is correct
8 Correct 35 ms 464 KB Output is correct
9 Correct 32 ms 952 KB Output is correct
10 Correct 82 ms 1104 KB Output is correct
11 Correct 87 ms 1488 KB Output is correct
12 Correct 129 ms 2128 KB Output is correct
13 Correct 177 ms 2252 KB Output is correct
14 Correct 240 ms 2740 KB Output is correct
15 Correct 215 ms 5532 KB Output is correct

Subtask #2
50.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5280 ms 18144 KB Output is correct
2 Correct 2863 ms 15136 KB Output is correct
3 Execution timed out 8031 ms 16212 KB Time limit exceeded
4 Correct 215 ms 3280 KB Output is correct
5 Correct 237 ms 4948 KB Output is correct
6 Correct 2278 ms 29800 KB Output is correct
7 Correct 1648 ms 21928 KB Output is correct
8 Execution timed out 8042 ms 63392 KB Time limit exceeded
9 Correct 1986 ms 15268 KB Output is correct
10 Execution timed out 8019 ms 77528 KB Time limit exceeded
11 Correct 4392 ms 19692 KB Output is correct
12 Correct 3643 ms 20280 KB Output is correct
13 Correct 7902 ms 20988 KB Output is correct
14 Execution timed out 8058 ms 37436 KB Time limit exceeded
15 Execution timed out 8039 ms 21916 KB Time limit exceeded
16 Execution timed out 8080 ms 25808 KB Time limit exceeded
17 Execution timed out 8039 ms 29172 KB Time limit exceeded