oj.uz

Submission #1092687

# Submission time Handle Problem Language Result Execution time Memory
1092687 2024-09-24T18:20:56 Z vjudge1 Regions (IOI09_regions) C++17
70 / 100
 8000 ms 47440 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
 
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
 
// #define endl '\n'
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i,l,r) for(auto i=l;i<r;i++)
#define fo(i,n) fore(i,0,n)
#define forex(i,r,l) for(auto i=r; i>=l;i--)
#define ffo(i,n) forex(i,n-1,0)
 
bool cmin(ll &a, ll b) { if(b<a){a=b;return 1;}return 0; }
bool cmax(ll &a, ll b) { if(b>a){a=b;return 1;}return 0; }
void valid(ll in) { cout<<((in)?"YES\n":"NO\n"); }
ll lcm(ll a, ll b) { return (a/gcd(a,b))*b; }
ll gauss(ll n) { return (n*(n+1))/2; }

const int N = 2e5 + 7;
int pa[N], h[N], el[N], tin[N], tout[N], timer, n, r, Q;
vi graph[N];
map<int, int> rd[N];
int ft[N];
void update(int i, int v) { for(; i<n+2; i+=lsb(i)) ft[i] += v; }
int query(int i) { int r = 0; for(; i>0; i-=lsb(i)) r += ft[i]; return r; }
void test_case() {
    cin >> n >> r >> Q;
    vector<vi> ord(r+1); 
    cin >> h[1];
    fore (i, 2, n+1) {
        cin >> pa[i];
        graph[pa[i]].pb(i);
        cin >> h[i];
    }
    if (r <= 500) {
        vector<vi> dp(501, vi(501, 0));
        function<void(int)> dfs = [&](int u) {
            rd[u][h[u]]++;
            for(int v: graph[u]) {
                dfs(v);
                if(sz(rd[v]) > sz(rd[u])) swap(rd[u], rd[v]);
                for (auto [k, vl]: rd[v]) {
                    rd[u][k] += vl;
                }
            }
            for (auto [k, vl]: rd[u]) dp[h[u]][k] += vl;
        };
        dfs(1);
        while (Q--) {
            int r1, r2;
            cin >> r1 >> r2;
            cout << dp[r1][r2] << endl;
        }
        return;
    }
    // int mx = 0;
    // fore (i, 1, r+1) mx = max(mx, sz(ord[i])); 
    // assert(mx <= 500);
    timer = 1;
    function<void(int)> dfs = [&](int u) {
        el[timer]=u;
        ord[h[u]].pb(u);
        tin[u] = timer++;
        for(int v: graph[u]) dfs(v);
        tout[u] = timer-1;
    };
    dfs(1);
    while (Q--) {
        int r1, r2;
        cin >> r1 >> r2;
        int ans = 0, l = 0;
        fo (i, sz(ord[r2])) update(tout[ord[r2][i]], +1);
        fo (i, sz(ord[r1])) {
            while(l < sz(ord[r2]) && tin[ord[r2][l]] < tin[ord[r1][i]]) {
                update(tout[ord[r2][l]], -1);
                l++;
            }
            ans += query(tout[ord[r1][i]]);
        }
        fore(i, l, sz(ord[r2])) update(tout[ord[r2][i]], -1);
        cout << ans << endl;
    }
}

int main() {
    int tt = 1;
    // cin >> tt;
    while(tt--) test_case();
}

Compilation message

regions.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
regions.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15448 KB Output is correct
2 Correct 6 ms 15412 KB Output is correct
3 Correct 7 ms 15448 KB Output is correct
4 Correct 9 ms 15448 KB Output is correct
5 Correct 10 ms 15448 KB Output is correct
6 Correct 17 ms 15704 KB Output is correct
7 Correct 20 ms 15704 KB Output is correct
8 Correct 23 ms 15784 KB Output is correct
9 Correct 49 ms 16728 KB Output is correct
10 Correct 58 ms 17240 KB Output is correct
11 Correct 72 ms 17752 KB Output is correct
12 Correct 151 ms 18256 KB Output is correct
13 Correct 125 ms 19280 KB Output is correct
14 Correct 119 ms 20304 KB Output is correct
15 Correct 292 ms 25688 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 25680 KB Output is correct
2 Correct 700 ms 25936 KB Output is correct
3 Correct 1165 ms 29776 KB Output is correct
4 Correct 267 ms 16304 KB Output is correct
5 Correct 310 ms 19536 KB Output is correct
6 Correct 1268 ms 18252 KB Output is correct
7 Correct 1728 ms 19172 KB Output is correct
8 Correct 1303 ms 28316 KB Output is correct
9 Correct 2610 ms 26444 KB Output is correct
10 Correct 3787 ms 35112 KB Output is correct
11 Correct 4674 ms 25240 KB Output is correct
12 Execution timed out 8039 ms 26704 KB Time limit exceeded
13 Execution timed out 8007 ms 27800 KB Time limit exceeded
14 Execution timed out 8038 ms 27156 KB Time limit exceeded
15 Execution timed out 8076 ms 35076 KB Time limit exceeded
16 Execution timed out 8048 ms 47440 KB Time limit exceeded
17 Execution timed out 8023 ms 44880 KB Time limit exceeded