답안 #1027026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1027026 2024-07-18T18:55:45 Z YassineBenYounes Regions (IOI09_regions) C++17
80 / 100
8000 ms 131072 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;
const int sq = 320;
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 <= r;i++){
        sort(all(vect[i]));
    }
    map<pii, int > pre;
    for(int i = 1; i <= r;i++){
        if(vect[i].size() >= sq){
            for(int b = 1; b <= r;b++){
                int ans = 0;
                for(int x : nodes[i]){
                    int l = lower_bound(all(vect[b]), tin[x]) - vect[b].begin();
                    int r = lower_bound(all(vect[b]), tout[x]) - vect[b].begin();
                    ans += r-l;
                }
                pre[{i, b}] = ans;
            }
        }
    }
    while(q--){
        int a, b;cin >> a >> b;
        int ans = 0;
        if(pre.find({a, b}) != pre.end()){
            cout << pre[{a, b}] << endl;
            continue;
        }
        /*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);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 15960 KB Output is correct
2 Correct 3 ms 15960 KB Output is correct
3 Correct 5 ms 16072 KB Output is correct
4 Correct 5 ms 15960 KB Output is correct
5 Correct 6 ms 15960 KB Output is correct
6 Correct 12 ms 15960 KB Output is correct
7 Correct 16 ms 15960 KB Output is correct
8 Correct 23 ms 15960 KB Output is correct
9 Correct 37 ms 16472 KB Output is correct
10 Correct 64 ms 16472 KB Output is correct
11 Correct 81 ms 16728 KB Output is correct
12 Correct 98 ms 17240 KB Output is correct
13 Correct 125 ms 16728 KB Output is correct
14 Correct 193 ms 17240 KB Output is correct
15 Correct 181 ms 19800 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1553 ms 20304 KB Output is correct
2 Correct 1786 ms 19008 KB Output is correct
3 Correct 2420 ms 21848 KB Output is correct
4 Correct 200 ms 16468 KB Output is correct
5 Correct 256 ms 18264 KB Output is correct
6 Correct 2583 ms 44040 KB Output is correct
7 Correct 2815 ms 46416 KB Output is correct
8 Correct 4110 ms 86352 KB Output is correct
9 Correct 1718 ms 24824 KB Output is correct
10 Runtime error 4972 ms 131072 KB Execution killed with signal 9
11 Correct 4212 ms 50104 KB Output is correct
12 Correct 4850 ms 26964 KB Output is correct
13 Correct 4957 ms 27220 KB Output is correct
14 Execution timed out 8023 ms 44392 KB Time limit exceeded
15 Execution timed out 8005 ms 32408 KB Time limit exceeded
16 Correct 6139 ms 37960 KB Output is correct
17 Execution timed out 8034 ms 62320 KB Time limit exceeded