oj.uz

Submission #1092667

# Submission time Handle Problem Language Result Execution time Memory
1092667 2024-09-24T17:49:47 Z vjudge1 Regions (IOI09_regions) C++17
60 / 100
 8000 ms 49484 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;
    }
    int mx = 0;
    fore (i, 1, r+1) mx = max(mx, sz(ord[i])); 
    assert(mx <= 500);
    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 10 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 24 ms 15704 KB Output is correct
8 Correct 26 ms 15704 KB Output is correct
9 Correct 56 ms 16728 KB Output is correct
10 Correct 55 ms 17248 KB Output is correct
11 Correct 88 ms 17760 KB Output is correct
12 Correct 166 ms 18520 KB Output is correct
13 Correct 107 ms 19544 KB Output is correct
14 Correct 118 ms 20308 KB Output is correct
15 Correct 272 ms 25948 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 25940 KB Output is correct
2 Correct 706 ms 26372 KB Output is correct
3 Correct 1153 ms 30292 KB Output is correct
4 Correct 256 ms 16216 KB Output is correct
5 Correct 330 ms 19252 KB Output is correct
6 Correct 6593 ms 17752 KB Output is correct
7 Correct 3743 ms 18648 KB Output is correct
8 Correct 2375 ms 27472 KB Output is correct
9 Correct 3717 ms 24656 KB Output is correct
10 Execution timed out 8080 ms 34208 KB Time limit exceeded
11 Execution timed out 8064 ms 23632 KB Time limit exceeded
12 Runtime error 94 ms 47184 KB Execution killed with signal 6
13 Runtime error 110 ms 46156 KB Execution killed with signal 6
14 Runtime error 109 ms 46604 KB Execution killed with signal 6
15 Runtime error 143 ms 49484 KB Execution killed with signal 6
16 Runtime error 98 ms 48976 KB Execution killed with signal 6
17 Runtime error 97 ms 48720 KB Execution killed with signal 6