oj.uz

Submission #1027015

# Submission time Handle Problem Language Result Execution time Memory
1027015 2024-07-18T18:38:04 Z YassineBenYounes Regions (IOI09_regions) C++17
75 / 100
 8000 ms 34640 KB 
#include<bits/stdc++.h>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
int dx[8] = {1, 0, 0, -1, 1, 1, -1, -1};
int dy[8] = {0, 1, -1, 0, 1, -1, -1, 1};
#define endl "\n"
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
////////////////////Only Clear Code//////////////////////////
 
void usaco_problem(){
    freopen("milkvisits.in", "r", stdin);
    freopen("milkvisits.out", "w", stdout);
}
 
void init(){
    #ifndef ONLINE_JUDGE
 
freopen("input.txt", "r", stdin);
 
freopen("output.txt", "w", stdout);
 
#endif // ONLINE_JUDGE
}
const int mx = 2e5+5;
const int LOG = 22;
const int inf = 1e9;
const ll mod = 998244353;

int arr[mx];

vi graph[mx];

int tin[mx], tout[mx];

int c = 0;

void dfs(int node, int p){
    tin[node] = c++;
    for(int adj : graph[node]){
        if(adj == p)continue;
        dfs(adj, node);
    }
    tout[node] = c++;
}

vi vect[mx];
vi nodes[mx];
int32_t main(){
    int n, r, q;cin >> n >> r >> q;
    for(int i = 1; i <= n;i++){
        if(i > 1){
            int a;cin >> a;
            graph[a].pb(i);
        }
        cin >> arr[i];
    }
    dfs(1, 1);
    for(int i = 1; i <= n;i++){
        vect[arr[i]].pb(tin[i]);
        nodes[arr[i]].pb(i);
    }
    for(int i = 1; i <= n;i++){
        sort(all(vect[i]));
    }
    while(q--){
        int a, b;cin >> a >> b;
        int ans = 0;
        /*cout << a << " " << b << endl;
        for(int x : vect[b]){
            cout << x << " ";
        }
        cout << endl;*/
        for(int i : nodes[a]){
            int l = lower_bound(all(vect[b]), tin[i]) - vect[b].begin();
            int r = lower_bound(all(vect[b]), tout[i]) - vect[b].begin();
            ans += r-l;
        }
        cout << ans << endl;
        cout.flush();
    }
}
 
/*
    NEVER GIVE UP!
    DOING SMTHNG IS BETTER THAN DOING NTHNG!!!
    Your Guide when stuck:
    - Continue keyword only after reading the whole input
    - Don't use memset with testcases
    - Check for corner cases(n=1, n=0)
    - Check where you declare n(Be careful of declaring it globally and in main)
*/

Compilation message

regions.cpp: In function 'void usaco_problem()':
regions.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen("milkvisits.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     freopen("milkvisits.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'void init()':
regions.cpp:40:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:42:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15960 KB Output is correct
2 Correct 3 ms 15960 KB Output is correct
3 Correct 3 ms 15960 KB Output is correct
4 Correct 5 ms 15960 KB Output is correct
5 Correct 6 ms 15960 KB Output is correct
6 Correct 13 ms 15960 KB Output is correct
7 Correct 17 ms 15960 KB Output is correct
8 Correct 18 ms 15960 KB Output is correct
9 Correct 36 ms 16472 KB Output is correct
10 Correct 74 ms 16472 KB Output is correct
11 Correct 80 ms 16724 KB Output is correct
12 Correct 96 ms 17240 KB Output is correct
13 Correct 144 ms 16728 KB Output is correct
14 Correct 211 ms 17240 KB Output is correct
15 Correct 201 ms 19800 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8013 ms 19984 KB Time limit exceeded
2 Execution timed out 8004 ms 18776 KB Time limit exceeded
3 Execution timed out 8083 ms 21848 KB Time limit exceeded
4 Correct 207 ms 17496 KB Output is correct
5 Correct 259 ms 19032 KB Output is correct
6 Correct 1008 ms 18520 KB Output is correct
7 Correct 1290 ms 19536 KB Output is correct
8 Correct 968 ms 24148 KB Output is correct
9 Correct 1754 ms 24144 KB Output is correct
10 Correct 3261 ms 29008 KB Output is correct
11 Correct 2999 ms 23628 KB Output is correct
12 Correct 4492 ms 25168 KB Output is correct
13 Correct 4979 ms 25424 KB Output is correct
14 Correct 6767 ms 25168 KB Output is correct
15 Execution timed out 8009 ms 29520 KB Time limit exceeded
16 Correct 6846 ms 34640 KB Output is correct
17 Execution timed out 8012 ms 33432 KB Time limit exceeded