Submission #960290

# Submission time Handle Problem Language Result Execution time Memory
960290 2024-04-10T07:38:50 Z hariaakas646 Regions (IOI09_regions) C++14
100 / 100
3622 ms 87096 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;


void usaco()
{
    freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
//    freopen("problem.out", "w", stdout);
}

int n, r, q;
vvi regions, graph;
vi pos, idx;
vvi val;
int cnt = 0;
vi st, en;
int timer = 0;
vvi euler;
vi vec;

void dfs(int x) {
    st[x] = ++timer;
    euler[pos[x]].pb(st[x]);
    frange(i, vec.size()) {
        val[i][pos[x]] += vec[i];
    }
    
    if(idx[pos[x]] != -1) {
        vec[idx[pos[x]]]++;
    }
    for(auto e : graph[x]) {
        
        dfs(e);
        
    }
    if(idx[pos[x]] != -1) {
        vec[idx[pos[x]]]--;
    }
    en[x] = timer;
}


int main() {
    // usaco();
    scd(n);
    scd(r);
    scd(q);

    graph = vvi(n+1);
    regions = vvi(r+1);
    pos = vi(n+1);

    scd(pos[1]);
    regions[pos[1]].pb(1);

    forr(i, 2, n+1) {
        int p, h;
        scd(p);
        scd(h);
        regions[h].pb(i);
        graph[p].pb(i);
        pos[i] = h;
    }
    int sq = sqrt(n);
    idx = vi(r+1, -1);
    forr(i, 1, r+1) {
        if(regions[i].size() >= sq) {
            idx[i] = val.size();
            val.pb(vi(n+1));
        }
    }
    st = en = vi(n+1);
    euler = vvi(r+1);
    vec = vi(val.size());
    dfs(1);

    frange(_, q) {
        int r1, r2;
        scd(r1);
        scd(r2);
        if(idx[r1] != -1) {
            printf("%d\n", val[idx[r1]][r2]);
        }
        else {
            // printf("man %d\n", r1);
            int tot = 0;
            for(auto e : regions[r1]) {
                tot += upper_bound(all(euler[r2]), en[e]) - lower_bound(all(euler[r2]), st[e]);
            }
            printf("%d\n", tot);
        }
        fflush(stdout);
    }
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:7:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define forr(i, j, k) for (int i = j; i < k; i++)
      |                                         ^
regions.cpp:8:22: note: in expansion of macro 'forr'
    8 | #define frange(i, j) forr(i, 0, j)
      |                      ^~~~
regions.cpp:47:5: note: in expansion of macro 'frange'
   47 |     frange(i, vec.size()) {
      |     ^~~~~~
regions.cpp: In function 'int main()':
regions.cpp:90:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |         if(regions[i].size() >= sq) {
      |            ~~~~~~~~~~~~~~~~~~^~~~~
regions.cpp: In function 'void usaco()':
regions.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
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:68:5: note: in expansion of macro 'scd'
   68 |     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:69:5: note: in expansion of macro 'scd'
   69 |     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:70:5: note: in expansion of macro 'scd'
   70 |     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:76:5: note: in expansion of macro 'scd'
   76 |     scd(pos[1]);
      |     ^~~
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:81:9: note: in expansion of macro 'scd'
   81 |         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:82:9: note: in expansion of macro 'scd'
   82 |         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:102:9: note: in expansion of macro 'scd'
  102 |         scd(r1);
      |         ^~~
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:103:9: note: in expansion of macro 'scd'
  103 |         scd(r2);
      |         ^~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 12 ms 344 KB Output is correct
8 Correct 19 ms 600 KB Output is correct
9 Correct 28 ms 856 KB Output is correct
10 Correct 45 ms 1232 KB Output is correct
11 Correct 75 ms 1644 KB Output is correct
12 Correct 87 ms 2148 KB Output is correct
13 Correct 130 ms 1880 KB Output is correct
14 Correct 209 ms 3160 KB Output is correct
15 Correct 219 ms 5704 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1375 ms 13660 KB Output is correct
2 Correct 1704 ms 9932 KB Output is correct
3 Correct 2266 ms 12532 KB Output is correct
4 Correct 179 ms 2808 KB Output is correct
5 Correct 223 ms 4852 KB Output is correct
6 Correct 345 ms 17192 KB Output is correct
7 Correct 795 ms 20396 KB Output is correct
8 Correct 751 ms 51544 KB Output is correct
9 Correct 1819 ms 14192 KB Output is correct
10 Correct 2329 ms 87096 KB Output is correct
11 Correct 3622 ms 15720 KB Output is correct
12 Correct 1053 ms 18080 KB Output is correct
13 Correct 1460 ms 18060 KB Output is correct
14 Correct 1608 ms 34152 KB Output is correct
15 Correct 2500 ms 23088 KB Output is correct
16 Correct 2310 ms 28388 KB Output is correct
17 Correct 2191 ms 43428 KB Output is correct