oj.uz

Submission #1092702

# Submission time Handle Problem Language Result Execution time Memory
1092702 2024-09-24T19:01:35 Z vjudge1 Regions (IOI09_regions) C++17
100 / 100
 3489 ms 38328 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 = 500;
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 5156 KB Output is correct
6 Correct 11 ms 5208 KB Output is correct
7 Correct 16 ms 5208 KB Output is correct
8 Correct 17 ms 5208 KB Output is correct
9 Correct 29 ms 5976 KB Output is correct
10 Correct 45 ms 5720 KB Output is correct
11 Correct 83 ms 5976 KB Output is correct
12 Correct 98 ms 6744 KB Output is correct
13 Correct 105 ms 5976 KB Output is correct
14 Correct 167 ms 6744 KB Output is correct
15 Correct 213 ms 11864 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1573 ms 10916 KB Output is correct
2 Correct 1711 ms 8868 KB Output is correct
3 Correct 2360 ms 14044 KB Output is correct
4 Correct 230 ms 6996 KB Output is correct
5 Correct 261 ms 10072 KB Output is correct
6 Correct 1078 ms 8524 KB Output is correct
7 Correct 1386 ms 9552 KB Output is correct
8 Correct 1083 ms 18512 KB Output is correct
9 Correct 1739 ms 15900 KB Output is correct
10 Correct 3489 ms 25424 KB Output is correct
11 Correct 2960 ms 15184 KB Output is correct
12 Correct 1059 ms 16720 KB Output is correct
13 Correct 1574 ms 17984 KB Output is correct
14 Correct 1931 ms 18788 KB Output is correct
15 Correct 2578 ms 25360 KB Output is correct
16 Correct 2682 ms 38328 KB Output is correct
17 Correct 2582 ms 36944 KB Output is correct