oj.uz

Submission #1092659

# Submission time Handle Problem Language Result Execution time Memory
1092659 2024-09-24T17:28:06 Z vjudge1 Regions (IOI09_regions) C++17
45 / 100
 8000 ms 37276 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];
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);
    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 2 ms 4952 KB Output is correct
2 Correct 2 ms 4984 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 5 ms 4952 KB Output is correct
5 Correct 6 ms 4952 KB Output is correct
6 Correct 16 ms 5208 KB Output is correct
7 Correct 17 ms 5208 KB Output is correct
8 Correct 18 ms 5208 KB Output is correct
9 Correct 31 ms 5976 KB Output is correct
10 Correct 66 ms 5464 KB Output is correct
11 Correct 127 ms 5976 KB Output is correct
12 Correct 134 ms 6488 KB Output is correct
13 Correct 234 ms 5976 KB Output is correct
14 Correct 591 ms 6676 KB Output is correct
15 Correct 546 ms 11604 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8016 ms 10828 KB Time limit exceeded
2 Execution timed out 8036 ms 8788 KB Time limit exceeded
3 Execution timed out 8052 ms 13656 KB Time limit exceeded
4 Correct 237 ms 6744 KB Output is correct
5 Correct 319 ms 9816 KB Output is correct
6 Correct 6642 ms 8280 KB Output is correct
7 Correct 3860 ms 9304 KB Output is correct
8 Correct 2429 ms 18260 KB Output is correct
9 Correct 3829 ms 15440 KB Output is correct
10 Execution timed out 8003 ms 24656 KB Time limit exceeded
11 Execution timed out 8069 ms 14160 KB Time limit exceeded
12 Execution timed out 8003 ms 15912 KB Time limit exceeded
13 Execution timed out 8020 ms 16976 KB Time limit exceeded
14 Execution timed out 8060 ms 15952 KB Time limit exceeded
15 Execution timed out 8013 ms 24200 KB Time limit exceeded
16 Execution timed out 8077 ms 37276 KB Time limit exceeded
17 Execution timed out 8013 ms 34384 KB Time limit exceeded