oj.uz

Submission #1092703

# Submission time Handle Problem Language Result Execution time Memory
1092703 2024-09-24T19:02:47 Z vjudge1 Regions (IOI09_regions) C++17
100 / 100
 3084 ms 38324 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, B = 400;
int pa[N], h[N], el[N], tin[N], tout[N], timer, n, r, Q;
vi graph[N], ots;
vector<vi> pr_ans;
void test_case() {
    cin >> n >> r >> Q;
    vector<vi> tins(r+1); 
    cin >> h[1];
    fore (i, 2, n+1) {
        cin >> pa[i];
        graph[pa[i]].pb(i);
        cin >> h[i];
    }
    timer = 1;
    function<void(int)> dfs = [&](int u) {
        el[timer] = u;
        tin[u] = timer++;
        tins[h[u]].pb(tin[u]);
        for(int v: graph[u]) dfs(v);
        tout[u] = timer-1;
    };
    dfs(1);
    fore (i, 1, r+1) {
        if (sz(tins[i]) > B) {
            ots.pb(i);
            vi dp(r+1, 0);
            int cnt = 0;
            function<void(int)> dfs2 = [&](int u) {
                cnt += (h[u] == i);
                dp[h[u]] += cnt;
                for(int v: graph[u]) dfs2(v);
                cnt -= (h[u] == i);
            };
            dfs2(1);
            pr_ans.pb(dp);
        }
    }
    while (Q--) {
        int r1, r2, ans = 0;
        cin >> r1 >> r2;
        if(sz(tins[r1]) <= B) {
            fo (i, sz(tins[r1])) {
                int u = el[tins[r1][i]];
                ans += upper_bound(all(tins[r2]), tout[u])-tins[r2].begin();
                ans -= lower_bound(all(tins[r2]), tin[u])-tins[r2].begin();
            }
        } else {
            fo (i, sz(ots)) if(ots[i] == r1) ans = pr_ans[i][r2];
        }
        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 2 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 4 ms 4952 KB Output is correct
5 Correct 5 ms 5112 KB Output is correct
6 Correct 11 ms 5208 KB Output is correct
7 Correct 16 ms 5180 KB Output is correct
8 Correct 19 ms 5208 KB Output is correct
9 Correct 31 ms 5976 KB Output is correct
10 Correct 49 ms 5720 KB Output is correct
11 Correct 79 ms 5976 KB Output is correct
12 Correct 82 ms 6744 KB Output is correct
13 Correct 122 ms 5976 KB Output is correct
14 Correct 187 ms 6744 KB Output is correct
15 Correct 237 ms 11864 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1517 ms 10908 KB Output is correct
2 Correct 1735 ms 8784 KB Output is correct
3 Correct 2420 ms 13904 KB Output is correct
4 Correct 215 ms 7000 KB Output is correct
5 Correct 301 ms 10072 KB Output is correct
6 Correct 526 ms 10064 KB Output is correct
7 Correct 1157 ms 10576 KB Output is correct
8 Correct 1010 ms 22608 KB Output is correct
9 Correct 1789 ms 16060 KB Output is correct
10 Correct 2683 ms 35408 KB Output is correct
11 Correct 3084 ms 15184 KB Output is correct
12 Correct 1050 ms 16668 KB Output is correct
13 Correct 1526 ms 18000 KB Output is correct
14 Correct 1857 ms 18792 KB Output is correct
15 Correct 2620 ms 25356 KB Output is correct
16 Correct 2684 ms 38324 KB Output is correct
17 Correct 2568 ms 36944 KB Output is correct