oj.uz

Submission #1092663

# Submission time Handle Problem Language Result Execution time Memory
1092663 2024-09-24T17:39:41 Z vjudge1 Regions (IOI09_regions) C++17
60 / 100
 8000 ms 46672 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], tin[N], tout[N], timer, n, r, Q;
vi graph[N];
map<int, int> rd[N];
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];
    }
    fore (i, 1, n+1) ord[h[i]].pb(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;
    }
    function<void(int)> dfs = [&](int 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;
        for(int e1: ord[r1]) {
            for(int e2: ord[r2]) {
                if(tin[e1] <= tin[e2] && tout[e2] <= tout[e1]) ans++;
            }
        }
        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 7 ms 15448 KB Output is correct
2 Correct 7 ms 15448 KB Output is correct
3 Correct 8 ms 15448 KB Output is correct
4 Correct 9 ms 15448 KB Output is correct
5 Correct 11 ms 15616 KB Output is correct
6 Correct 18 ms 15704 KB Output is correct
7 Correct 22 ms 15704 KB Output is correct
8 Correct 26 ms 15704 KB Output is correct
9 Correct 59 ms 16728 KB Output is correct
10 Correct 66 ms 17240 KB Output is correct
11 Correct 95 ms 17740 KB Output is correct
12 Correct 148 ms 18524 KB Output is correct
13 Correct 96 ms 19548 KB Output is correct
14 Correct 135 ms 20316 KB Output is correct
15 Correct 243 ms 25948 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 26088 KB Output is correct
2 Correct 682 ms 26448 KB Output is correct
3 Correct 1230 ms 30288 KB Output is correct
4 Correct 238 ms 16216 KB Output is correct
5 Correct 312 ms 19288 KB Output is correct
6 Correct 6592 ms 17796 KB Output is correct
7 Correct 3715 ms 18632 KB Output is correct
8 Correct 2414 ms 27472 KB Output is correct
9 Correct 3750 ms 24656 KB Output is correct
10 Execution timed out 8093 ms 34164 KB Time limit exceeded
11 Execution timed out 8047 ms 23732 KB Time limit exceeded
12 Execution timed out 8089 ms 25164 KB Time limit exceeded
13 Execution timed out 8016 ms 26452 KB Time limit exceeded
14 Execution timed out 8045 ms 25420 KB Time limit exceeded
15 Execution timed out 8045 ms 33596 KB Time limit exceeded
16 Execution timed out 8080 ms 46672 KB Time limit exceeded
17 Execution timed out 8083 ms 43872 KB Time limit exceeded