oj.uz

답안 #914019

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
914019 2024-01-20T19:22:23 Z VMaksimoski008 Regions (IOI09_regions) C++14
80 / 100
 8000 ms 22752 KB 
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 5;
const double eps = 1e-9;

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int n, r, q, home[maxn], in[maxn], out[maxn], timer = 0;
vector<vector<int> > graph;
vector<vector<pii> > by_home;

void dfs(int u) {
    in[u] = timer++;

    for(int &v : graph[u])
        dfs(v);

    out[u] = timer;
}

int32_t main() {
    setIO();

    cin >> n >> r >> q;
    graph.resize(n+1);
    by_home.resize(r+1);
    
    cin >> home[1];

    for(int i=2; i<=n; i++) {
        int p;
        cin >> p >> home[i];
        graph[p].push_back(i);
    }

    dfs(1);

    for(int i=1; i<=n; i++)
        by_home[home[i]].push_back({ in[i], out[i] });
    for(int i=1; i<=r; i++)
        sort(all(by_home[i]));

    while(q--) {
        int r1, r2, ans = 0;
        cin >> r1 >> r2;

        for(pii &u : by_home[r1]) {
            //cout << u.first << " " << u.second << '\n';
            int l=0, r=sz(by_home[r2])-1;
            int p1 = 1e9;

            while(l <= r) {
                int mid = (l + r) / 2;
                if(by_home[r2][mid].first > u.first) p1 = mid, r = mid - 1;
                else l = mid + 1;
            }

            if(p1 == 1e9) continue;
            
            l=p1, r=sz(by_home[r2])-1;
            int p2 = 1e9;

            while(l <= r) {
                int mid = (l + r) / 2;
                if(by_home[r2][mid].first < u.second) p2 = mid, l = mid + 1;
                else r = mid - 1;
            }

            if(p2 == 1e9) continue;

            ans += (p2 - p1 + 1);
        }

        cout << ans << '\n';
        cout.flush();
    }
    
    return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 2 ms 2392 KB Output is correct
5 Correct 5 ms 2392 KB Output is correct
6 Correct 9 ms 2392 KB Output is correct
7 Correct 12 ms 2392 KB Output is correct
8 Correct 15 ms 2648 KB Output is correct
9 Correct 21 ms 3156 KB Output is correct
10 Correct 36 ms 3156 KB Output is correct
11 Correct 64 ms 3416 KB Output is correct
12 Correct 81 ms 3928 KB Output is correct
13 Correct 89 ms 3928 KB Output is correct
14 Correct 139 ms 4636 KB Output is correct
15 Correct 175 ms 6760 KB Output is correct

Subtask #2
65.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8051 ms 8140 KB Time limit exceeded
2 Execution timed out 8096 ms 6972 KB Time limit exceeded
3 Execution timed out 8026 ms 9688 KB Time limit exceeded
4 Correct 126 ms 4696 KB Output is correct
5 Correct 228 ms 5836 KB Output is correct
6 Correct 717 ms 6188 KB Output is correct
7 Correct 924 ms 7480 KB Output is correct
8 Correct 771 ms 11704 KB Output is correct
9 Correct 1217 ms 13684 KB Output is correct
10 Correct 2898 ms 17556 KB Output is correct
11 Correct 2353 ms 14604 KB Output is correct
12 Correct 2298 ms 15704 KB Output is correct
13 Correct 2806 ms 15664 KB Output is correct
14 Correct 3455 ms 15928 KB Output is correct
15 Correct 4330 ms 19536 KB Output is correct
16 Correct 5088 ms 22752 KB Output is correct
17 Execution timed out 8070 ms 21944 KB Time limit exceeded