oj.uz

답안 #649637

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
649637 2022-10-11T07:29:12 Z mychecksedad Regions (IOI09_regions) C++17
0 / 100
 5017 ms 131072 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;


int n, q, r, a[N], ans[505][505], tin[N], tout[N], timer = 0;
vector<int> g[N], R[N], path, pos[N];
map<pair<int, int>, pair<bool, int>> m;
void dfs(int v, int p){
    bool ok = 1;
    for(int u: g[v]){
        if(u == p) continue;
        dfs(u, v);
        if(ok){
            ok = 0;
            R[v].swap(R[u]);
            continue;
        }
        for(int j = 1; j <= r; ++j) R[v][j] += R[u][j];
        R[u].clear();
    }
    for(int j = 1; j <= r; ++j) ans[a[v]][j] += R[v][j];
    R[v][a[v]]++;    
}
void dfs1(int v, int p){
    path.pb(v);
    tin[v] = timer++;
    R[a[v]].pb(v);
    for(int u: g[v]){
        if(u == p) continue;
        dfs1(u, v);
    }
    path.pb(v);
    tout[v] = timer++;
}

void solve(){
    cin >> n >> r >> q;
    cin >> a[1];
    for(int i = 2; i <= n; ++i){
        int x; cin >> x >> a[i];
        g[x].pb(i);
        g[i].pb(x);
    }
    if(r <= 500){
        for(int i = 0; i <= r; ++i) for(int j = 0; j <= r; ++j) ans[i][j] = 0;
        dfs(1, 1);
        for(;q--;){
            int a, b; cin >> a >> b;
            cout << ans[a][b] << endl;
        }
    }else{
        dfs1(1, 1);
        for(int j = 0; j < path.size(); ++j){
            pos[a[path[j]]].pb(j);
        }
        for(;q--;){
            int a, b; cin >> a >> b;
            if(m[{a, b}].first){
                cout << m[{a, b}].second << endl;
                continue;
            }
            int ans = 0;
            if(R[a].size() < R[b].size())
                for(int v: R[a]){
                    ans += upper_bound(all(pos[b]), tout[v]) - upper_bound(all(pos[b]), tin[v]);
                }
            else
                for(int v: R[b]){
                    ans += int(pos[a].size()) - (upper_bound(all(pos[a]), tout[v]) - upper_bound(all(pos[a]), tin[v]));
                }
            cout << ans/2 << endl;
            m[{a, b}] = {1, ans/2};
        }
    }
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        // cout << '\n';
    }
    return 0;
 
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int j = 0; j < path.size(); ++j){
      |                        ~~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:96:16: warning: unused variable 'aa' [-Wunused-variable]
   96 |     int T = 1, aa;
      |                ^~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 88 ms 131072 KB Execution killed with signal 11
2 Runtime error 112 ms 131072 KB Execution killed with signal 11
3 Runtime error 102 ms 131072 KB Execution killed with signal 11
4 Runtime error 87 ms 131072 KB Execution killed with signal 11
5 Runtime error 93 ms 131072 KB Execution killed with signal 11
6 Runtime error 92 ms 131072 KB Execution killed with signal 11
7 Runtime error 103 ms 131072 KB Execution killed with signal 11
8 Runtime error 92 ms 131072 KB Execution killed with signal 11
9 Runtime error 96 ms 131072 KB Execution killed with signal 11
10 Runtime error 102 ms 131072 KB Execution killed with signal 11
11 Runtime error 116 ms 131072 KB Execution killed with signal 11
12 Runtime error 108 ms 131072 KB Execution killed with signal 11
13 Runtime error 100 ms 131072 KB Execution killed with signal 11
14 Runtime error 128 ms 131072 KB Execution killed with signal 11
15 Runtime error 116 ms 131072 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 112 ms 131072 KB Execution killed with signal 11
2 Runtime error 119 ms 131072 KB Execution killed with signal 11
3 Runtime error 126 ms 131072 KB Execution killed with signal 11
4 Incorrect 315 ms 74728 KB Output isn't correct
5 Incorrect 401 ms 76652 KB Output isn't correct
6 Incorrect 388 ms 76804 KB Output isn't correct
7 Incorrect 825 ms 77308 KB Output isn't correct
8 Incorrect 1284 ms 85052 KB Output isn't correct
9 Incorrect 2139 ms 90984 KB Output isn't correct
10 Incorrect 4177 ms 97340 KB Output isn't correct
11 Incorrect 4543 ms 97428 KB Output isn't correct
12 Incorrect 1434 ms 89008 KB Output isn't correct
13 Incorrect 2277 ms 91836 KB Output isn't correct
14 Incorrect 2390 ms 93576 KB Output isn't correct
15 Incorrect 5017 ms 99480 KB Output isn't correct
16 Incorrect 4404 ms 105372 KB Output isn't correct
17 Incorrect 4025 ms 104020 KB Output isn't correct