oj.uz

Submission #960286

# Submission time Handle Problem Language Result Execution time Memory
960286 2024-04-10T07:28:57 Z hariaakas646 Regions (IOI09_regions) C++14
85 / 100
 8000 ms 85648 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]);
    for(auto e : vec) {
        // printf("%d %d\n", e, x);
        val[e][pos[x]]++;
    }
    if(idx[pos[x]] != -1) {
        vec.pb(idx[pos[x]]);
    }
    for(auto e : graph[x]) {
        
        dfs(e);
        
    }
    if(idx[pos[x]] != -1) {
        vec.pop_back();
    }
    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);
    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 '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:101:9: note: in expansion of macro 'scd'
  101 |         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:102:9: note: in expansion of macro 'scd'
  102 |         scd(r2);
      |         ^~~

Subtask #1
15.0 / 15.0

# 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 4 ms 344 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 13 ms 344 KB Output is correct
8 Correct 18 ms 600 KB Output is correct
9 Correct 28 ms 856 KB Output is correct
10 Correct 55 ms 1112 KB Output is correct
11 Correct 75 ms 1624 KB Output is correct
12 Correct 91 ms 2292 KB Output is correct
13 Correct 127 ms 1900 KB Output is correct
14 Correct 207 ms 3160 KB Output is correct
15 Correct 209 ms 5704 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1957 ms 13696 KB Output is correct
2 Correct 1796 ms 9972 KB Output is correct
3 Correct 3618 ms 12588 KB Output is correct
4 Correct 164 ms 2932 KB Output is correct
5 Correct 247 ms 4844 KB Output is correct
6 Correct 1350 ms 17208 KB Output is correct
7 Correct 1175 ms 20408 KB Output is correct
8 Execution timed out 8009 ms 50792 KB Time limit exceeded
9 Correct 1794 ms 14188 KB Output is correct
10 Execution timed out 8066 ms 85648 KB Time limit exceeded
11 Correct 3588 ms 15724 KB Output is correct
12 Correct 1171 ms 17912 KB Output is correct
13 Correct 2013 ms 18088 KB Output is correct
14 Correct 2366 ms 34160 KB Output is correct
15 Correct 4964 ms 23136 KB Output is correct
16 Correct 7551 ms 28504 KB Output is correct
17 Execution timed out 8083 ms 42264 KB Time limit exceeded