oj.uz

답안 #961203

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961203 2024-04-11T16:52:05 Z steveonalex Regions (IOI09_regions) C++17
0 / 100
 82 ms 27424 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}

ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return 63 - __builtin_clzll(mask);}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }

template <class T>
    void printArr(T& container, char separator = ' ', char finish = '\n'){
        for(auto item: container) cout << item << separator;
        cout << finish;
    }

template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

#pragma GCC optimize("O3,avx2")

const long N = 2e5 + 69, R = 25000;

long n, rr, q;
vector<long> graph[N];
vector<long> area[R], vaix[R], king[R];
long l[N], r[N];
long dfs_cnt = 0;

void dfs(long u){
    l[u] = r[u] = ++dfs_cnt;
    for(long v: graph[u]){
        dfs(v);
        maximize(r[u], r[v]);
    }
}

ll calc1(long u, long v){
    ll ans = 0;
    for(long i: vaix[u]) {
        ans += upper_bound(ALL(area[v]), r[i]) - lower_bound(ALL(area[v]), l[i]);
    }
    return ans;
}

bool compare(long a, long b){return l[a] < l[b];}

ll calc2(long u, long v){
    ll ans = 0;
    if (area[v].size() * 3 <= area[u].size()){
        long x=  0, y = 0;
        for(long i: vaix[v]){
            while(x < king[u].size() && king[u][x] < l[i]) x++;
            ans += (int)king[u].size() - x;
            while(y < area[u].size() && area[u][y] <= l[i]) y++;
            ans -= (int)area[u].size() - y;
        }
        return ans;
    }
    for(long i: vaix[v]){
        long x = lower_bound(ALL(king[u]), l[i]) - king[u].begin();
        ans += king[u].size() - x;
        long y = upper_bound(ALL(area[u]), l[i]) - area[u].begin();
        ans -= area[u].size() - y;
    }
    return ans;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> rr >> q;
    long h; cin >> h; vaix[h].push_back(1);
    for(long i = 2; i<=n; ++i){
        long p, h; cin >> p >> h;
        graph[p].push_back(i);
        vaix[h].push_back(i);
    }

    dfs(1);

    for(long i= 1; i<=rr; ++i){
        for(long v: vaix[i]) {
            area[i].push_back(l[v]);
            king[i].push_back(r[v]);
        }
        sort(ALL(vaix[i]), compare);
        sort(ALL(area[i]));
        sort(ALL(king[i]));
    }

    map<pair<long, long>, long> mp;
    while(q--){
        long r1, r2; cin >> r1 >> r2;
        if (mp.count({r1, r2})) {
            cout << mp[{r1, r2}] << "\n";
            continue;
        }
        if (area[r1].size() <= area[r2].size()) {
            cout << (mp[{r1, r2}] = calc1(r1, r2)) << "\n";
        }
        else{
            cout << (mp[{r1, r2}] = calc2(r1, r2)) << "\n";
        }
    }
    
    return 0;
}

Compilation message

regions.cpp:47:31: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
   47 | #pragma GCC optimize("O3,avx2")
      |                               ^
regions.cpp:57:16: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   57 | void dfs(long u){
      |                ^
regions.cpp:65:24: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   65 | ll calc1(long u, long v){
      |                        ^
regions.cpp:73:28: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   73 | bool compare(long a, long b){return l[a] < l[b];}
      |                            ^
regions.cpp:75:24: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   75 | ll calc2(long u, long v){
      |                        ^
regions.cpp: In function 'll calc2(long int, long int)':
regions.cpp:80:21: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             while(x < king[u].size() && king[u][x] < l[i]) x++;
      |                   ~~^~~~~~~~~~~~~~~~
regions.cpp:82:21: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             while(y < area[u].size() && area[u][y] <= l[i]) y++;
      |                   ~~^~~~~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:96:14: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   96 | int main(void){
      |              ^

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4 ms 9816 KB Time limit exceeded (wall clock)
2 Execution timed out 2 ms 9816 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 9816 KB Time limit exceeded (wall clock)
4 Execution timed out 2 ms 9816 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 9816 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 9972 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 9816 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 9816 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 10328 KB Time limit exceeded (wall clock)
10 Execution timed out 5 ms 10328 KB Time limit exceeded (wall clock)
11 Execution timed out 6 ms 10900 KB Time limit exceeded (wall clock)
12 Execution timed out 8 ms 11480 KB Time limit exceeded (wall clock)
13 Execution timed out 9 ms 11352 KB Time limit exceeded (wall clock)
14 Execution timed out 12 ms 12012 KB Time limit exceeded (wall clock)
15 Execution timed out 11 ms 13776 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 24 ms 14808 KB Time limit exceeded (wall clock)
2 Execution timed out 30 ms 14296 KB Time limit exceeded (wall clock)
3 Execution timed out 33 ms 16076 KB Time limit exceeded (wall clock)
4 Execution timed out 11 ms 11864 KB Time limit exceeded (wall clock)
5 Execution timed out 15 ms 12968 KB Time limit exceeded (wall clock)
6 Execution timed out 18 ms 13076 KB Time limit exceeded (wall clock)
7 Execution timed out 27 ms 14456 KB Time limit exceeded (wall clock)
8 Execution timed out 31 ms 18244 KB Time limit exceeded (wall clock)
9 Execution timed out 61 ms 21440 KB Time limit exceeded (wall clock)
10 Execution timed out 70 ms 24004 KB Time limit exceeded (wall clock)
11 Execution timed out 82 ms 21264 KB Time limit exceeded (wall clock)
12 Execution timed out 79 ms 21876 KB Time limit exceeded (wall clock)
13 Execution timed out 67 ms 21988 KB Time limit exceeded (wall clock)
14 Execution timed out 81 ms 22256 KB Time limit exceeded (wall clock)
15 Execution timed out 68 ms 24952 KB Time limit exceeded (wall clock)
16 Execution timed out 60 ms 27184 KB Time limit exceeded (wall clock)
17 Execution timed out 66 ms 27424 KB Time limit exceeded (wall clock)