oj.uz

Submission #524527

# Submission time Handle Problem Language Result Execution time Memory
524527 2022-02-09T12:15:43 Z AmirElarbi Regions (IOI09_regions) C++14
0 / 100
 28 ms 38676 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e9
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9+7;
const int nax = 2e5+5;
vi adj[nax], node;
int a[nax], tin[nax],tout[nax], cnt = 0, vis[nax],freq[nax];
vi v[nax];
map<int,int> res[nax];
void dfs(int u, int p){
    node.pb(u);
    tin[u] = cnt;
    cnt++;
    for(auto x : adj[u])
        if(p != x) dfs(x,u);
    tout[u] = cnt-1;
}
int main(){ 
    optimise;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int n,r,q;
    cin >> n >> r >> q >> a[0];
    for (int i = 1; i < n; ++i)
    {
        int b;
        cin >> b >> a[i]; 
        b--;
        adj[i].pb(b), adj[b].pb(i);
    }
    dfs(0,0);
    for (int i = 0; i < n; ++i)
    {
        v[a[node[i]]].pb(i);
    }
    int mxk = sqrt(n);
    for (int i = 0; i < n; ++i)
    {
        if(vis[a[node[i]]]) continue;
        if(v[a[node[i]]].size() <= mxk) continue;
        vis[a[node[i]]] = 1;
        memset(freq,0,sizeof freq);
        for(auto x : v[a[node[i]]]){
            int l = tin[node[x]], r = tout[node[x]];
            freq[l]++, freq[r+1]--;
        }
        res[a[node[i]]][a[node[0]]] += freq[0]; 
        for (int j = 1; j < n; ++j)
        {
            freq[j] += freq[j-1];
            res[a[node[i]]][a[node[j]]] += freq[j]; 
        }
    }
    for (int i = 0; i < q; ++i)
    {
        int xu,xv, ans = 0;
        cin >> xu >> xv;
        if(v[xu].size() <= mxk){
            for(auto x : v[xu]){
                int l = tin[node[x]], r = tout[node[x]]; 
                int p1 = upper_bound(v[xv].begin(), v[xv].end(), r) - v[xv].begin(),
                    p2 = upper_bound(v[xv].begin(), v[xv].end(), l)- v[xv].begin();
                
                if(p1) p1--, ans += max(p1-p2+1,0);
            }
        }else ans = res[xu][xv];
        cout << ans << endl;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:60:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |         if(v[a[node[i]]].size() <= mxk) continue;
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~
regions.cpp:78:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |         if(v[xu].size() <= mxk){
      |            ~~~~~~~~~~~~~^~~~~~
regions.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 19144 KB Unexpected end of file - int32 expected
2 Incorrect 11 ms 19144 KB Unexpected end of file - int32 expected
3 Incorrect 11 ms 19116 KB Unexpected end of file - int32 expected
4 Runtime error 25 ms 38676 KB Execution killed with signal 11
5 Runtime error 26 ms 38668 KB Execution killed with signal 11
6 Incorrect 11 ms 19144 KB Unexpected end of file - int32 expected
7 Incorrect 11 ms 19144 KB Unexpected end of file - int32 expected
8 Runtime error 25 ms 38640 KB Execution killed with signal 11
9 Incorrect 11 ms 19092 KB Unexpected end of file - int32 expected
10 Runtime error 24 ms 38600 KB Execution killed with signal 11
11 Incorrect 11 ms 19144 KB Unexpected end of file - int32 expected
12 Runtime error 26 ms 38628 KB Execution killed with signal 11
13 Runtime error 25 ms 38600 KB Execution killed with signal 11
14 Incorrect 11 ms 19144 KB Unexpected end of file - int32 expected
15 Incorrect 11 ms 19144 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 38628 KB Execution killed with signal 11
2 Runtime error 24 ms 38580 KB Execution killed with signal 11
3 Incorrect 11 ms 19144 KB Unexpected end of file - int32 expected
4 Runtime error 26 ms 38600 KB Execution killed with signal 11
5 Runtime error 28 ms 38664 KB Execution killed with signal 11
6 Incorrect 11 ms 19144 KB Unexpected end of file - int32 expected
7 Incorrect 11 ms 19176 KB Unexpected end of file - int32 expected
8 Runtime error 25 ms 38600 KB Execution killed with signal 11
9 Incorrect 12 ms 19096 KB Unexpected end of file - int32 expected
10 Incorrect 11 ms 19088 KB Unexpected end of file - int32 expected
11 Runtime error 25 ms 38596 KB Execution killed with signal 11
12 Incorrect 11 ms 19144 KB Unexpected end of file - int32 expected
13 Runtime error 24 ms 38628 KB Execution killed with signal 11
14 Incorrect 12 ms 19144 KB Unexpected end of file - int32 expected
15 Incorrect 11 ms 19144 KB Unexpected end of file - int32 expected
16 Incorrect 12 ms 19144 KB Unexpected end of file - int32 expected
17 Incorrect 11 ms 19144 KB Unexpected end of file - int32 expected