oj.uz

Submission #517059

# Submission time Handle Problem Language Result Execution time Memory
517059 2022-01-22T13:02:27 Z Yuisuyuno Regions (IOI09_regions) C++14
31 / 100
 8000 ms 32224 KB 
//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define N 200005
#define remain(x) if (x > MOD) x -= MOD
#define ii pair<int, int>
#define iiii pair< ii , ii >
#define viiii vector< iiii >
#define vi vector<int>
#define vii vector< ii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "test"
#define int long long

using namespace std;

typedef long double ld;
const int inf = 1e10;
const int minf = -1e10;

int n, r, q;
int id[N], in[N], ou[N], cnt;
vector<int> g[N];
vector<int> reg[25005], node[25005];
int ans[450][25005], ID[25005];

void readfile()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    if (fopen(Task".inp","r"))
    {
        freopen(Task".inp","r",stdin);
        //freopen(Task".out","w",stdout);
    }
    cin >> n >> r >> q; int x; cin >> x; id[1] = x; node[x].pb(1);
    for(int i=2; i<=n; i++){
        int x, y; cin >> x >> y;
        g[x].pb(i);
        id[i] = y;
        node[y].pb(i);
    }
}

void dfs(int u){
    in[u] = ++cnt;
    reg[id[u]].pb(in[u]);
    for(auto v : g[u]){
        dfs(v);
    }
    ou[u] = ++cnt;
}

bool is_in(int inn, int oun){
    return in[oun] <= in[inn] && in[inn] < ou[oun];
}

void proc()
{
    dfs(1);
    int cnt = 0;
    int K = sqrt(n);
    for(int r1=1; r1<=r; r1++){
        if (node[r1].size()==0) continue;
        if (node[r1].size()<K) continue;
        cnt++;
        ID[r1] = cnt;
        for(auto x : node[r1]){
            for(int i=1; i<=n; i++) if (i!=x){
                if (is_in(i,x)) ans[cnt][id[i]]++;
            }
        }
    }
    while (q--){
        int u, v;
        cin >> u >> v;
        int res = 0;
        if (node[u].size()>=K){
            cout << ans[ID[u]][id[v]] << '\n';
            cout.flush();
            continue;
        }
        for(auto x : node[u]){
            int itr = lower_bound(all(reg[v]),ou[x])-reg[v].begin();
            int itl = lower_bound(all(reg[v]),in[x])-reg[v].begin();
            res += itr - itl;
        }
        cout << res << '\n';
        cout.flush();
    }
}

signed main()
{
    readfile();
    proc();
    return 0;
}

Compilation message

regions.cpp: In function 'void proc()':
regions.cpp:71:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   71 |         if (node[r1].size()<K) continue;
      |             ~~~~~~~~~~~~~~~^~
regions.cpp:84:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   84 |         if (node[u].size()>=K){
      |             ~~~~~~~~~~~~~~^~~
regions.cpp: In function 'void readfile()':
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(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6216 KB Output isn't correct
2 Incorrect 3 ms 6216 KB Output isn't correct
3 Correct 5 ms 6112 KB Output is correct
4 Correct 7 ms 6216 KB Output is correct
5 Correct 12 ms 6216 KB Output is correct
6 Correct 23 ms 6216 KB Output is correct
7 Correct 27 ms 6216 KB Output is correct
8 Correct 33 ms 6344 KB Output is correct
9 Correct 61 ms 6728 KB Output is correct
10 Correct 72 ms 6968 KB Output is correct
11 Correct 121 ms 7376 KB Output is correct
12 Correct 139 ms 7880 KB Output is correct
13 Correct 186 ms 7896 KB Output is correct
14 Incorrect 356 ms 8704 KB Output isn't correct
15 Incorrect 289 ms 10728 KB Output isn't correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 7559 ms 12424 KB Output isn't correct
2 Incorrect 7544 ms 11644 KB Output isn't correct
3 Execution timed out 8082 ms 14092 KB Time limit exceeded
4 Correct 271 ms 8608 KB Output is correct
5 Correct 414 ms 9904 KB Output is correct
6 Incorrect 4088 ms 13672 KB Output isn't correct
7 Incorrect 3863 ms 15836 KB Output isn't correct
8 Execution timed out 8087 ms 23788 KB Time limit exceeded
9 Correct 2499 ms 19012 KB Output is correct
10 Execution timed out 8079 ms 32224 KB Time limit exceeded
11 Correct 4310 ms 20128 KB Output is correct
12 Execution timed out 8058 ms 21060 KB Time limit exceeded
13 Execution timed out 8051 ms 21088 KB Time limit exceeded
14 Execution timed out 8087 ms 21652 KB Time limit exceeded
15 Execution timed out 8084 ms 24376 KB Time limit exceeded
16 Execution timed out 8099 ms 27520 KB Time limit exceeded
17 Execution timed out 8034 ms 28144 KB Time limit exceeded