oj.uz

Submission #856375

# Submission time Handle Problem Language Result Execution time Memory
856375 2023-10-03T09:24:55 Z hqminhuwu Regions (IOI09_regions) C++17
0 / 100
 6 ms 16984 KB 
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = _b; _a <= _c; ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> _c;)
#define forf(_a,_b,_c) for(_a = _b; _a < _c; ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 2e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

int fst[N],lst[N],f[N],res[500][N],par[N],cnt[N],n,r,q,cur;
vector <int> a[N],w[N],ww[N];
void go (int u){
    fst[u] = ++cur;
    w[f[u]].pb(cur);
    ww[f[u]].pb(u);
    for (int v : a[u])
        go(v);
    lst[u] = cur;
}

int od[N];
void dfs (int u, int sum, int x){
    res[f[u]][od[x]] += sum;;
    sum += (f[u] == x);
    for (int v : a[u])
        dfs(v,sum,x);
}

int i,u,v;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
       freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif
    cin >> n >> r >> q;
    cin >> f[1];
    cnt[f[1]]++;
    forr (i,2,n)
        cin >> par[i],a[par[i]].pb(i),
        cin >> f[i],cnt[f[i]]++;
    go(1);
    int numcmp = 0;
    forr (i,1,r){
        if (cnt[i] < sqrt(n))
            continue;
        od[i] = ++numcmp;
        dfs(1,0,i);
    }
    while (q--){
        cin >> u >> v;
        if (od[u])
            cout <<res[v][od[u]] << endl;
        else {
            int ans = 0;
            for (int i : ww[u]){
                ans += upper_bound(all(w[v]),lst[i]) - lower_bound(all(w[v]),fst[i]);
            }
                cout << ans << endl;
        }
    }
    return 0;
}
/*



*/

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:47:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:47:48: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
      |                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
2 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
3 Incorrect 5 ms 16728 KB Unexpected end of file - int32 expected
4 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
5 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
6 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
7 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
8 Incorrect 5 ms 16728 KB Unexpected end of file - int32 expected
9 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
10 Incorrect 5 ms 16728 KB Unexpected end of file - int32 expected
11 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
12 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
13 Incorrect 5 ms 16984 KB Unexpected end of file - int32 expected
14 Incorrect 5 ms 16728 KB Unexpected end of file - int32 expected
15 Incorrect 5 ms 16728 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
2 Incorrect 6 ms 16880 KB Unexpected end of file - int32 expected
3 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
4 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
5 Incorrect 5 ms 16728 KB Unexpected end of file - int32 expected
6 Incorrect 4 ms 16820 KB Unexpected end of file - int32 expected
7 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
8 Incorrect 5 ms 16728 KB Unexpected end of file - int32 expected
9 Incorrect 4 ms 16980 KB Unexpected end of file - int32 expected
10 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
11 Incorrect 5 ms 16728 KB Unexpected end of file - int32 expected
12 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
13 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
14 Incorrect 6 ms 16924 KB Unexpected end of file - int32 expected
15 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
16 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected
17 Incorrect 4 ms 16728 KB Unexpected end of file - int32 expected