oj.uz

Submission #516289

# Submission time Handle Problem Language Result Execution time Memory
516289 2022-01-21T03:32:06 Z Yuisuyuno Regions (IOI09_regions) C++14
35 / 100
 8000 ms 32268 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;
    for(int r1=1; r1<=r; r1++){
        if (node[r1].size()<447) 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()>=447){
            cout << ans[ID[u]][id[v]] << '\n';
            cout.flush();
            continue;
        }
        for(auto x : node[u]){
            //cout << in[x] << ' ' << ou[x] << '\n';
            int itr = lower_bound(all(reg[v]),ou[x])-reg[v].begin();
            int itl = lower_bound(all(reg[v]),in[x])-reg[v].begin();
            //cout << itr << ' ' << itl << '\n';
            res += itr - itl;
        }
        cout << res << '\n';
        cout.flush();
    }
}

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

Compilation message

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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6088 KB Output is correct
2 Correct 3 ms 6216 KB Output is correct
3 Correct 6 ms 6216 KB Output is correct
4 Correct 7 ms 6216 KB Output is correct
5 Correct 8 ms 6216 KB Output is correct
6 Correct 22 ms 6216 KB Output is correct
7 Correct 17 ms 6216 KB Output is correct
8 Correct 42 ms 6388 KB Output is correct
9 Correct 50 ms 6728 KB Output is correct
10 Correct 87 ms 6984 KB Output is correct
11 Correct 107 ms 7368 KB Output is correct
12 Correct 156 ms 8032 KB Output is correct
13 Correct 184 ms 7880 KB Output is correct
14 Correct 277 ms 8608 KB Output is correct
15 Correct 247 ms 10696 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 7303 ms 12416 KB Output isn't correct
2 Incorrect 7642 ms 11624 KB Output isn't correct
3 Execution timed out 8039 ms 14188 KB Time limit exceeded
4 Correct 259 ms 8604 KB Output is correct
5 Correct 365 ms 9896 KB Output is correct
6 Incorrect 3992 ms 13820 KB Output isn't correct
7 Incorrect 2481 ms 13124 KB Output isn't correct
8 Execution timed out 8015 ms 23528 KB Time limit exceeded
9 Correct 2164 ms 19012 KB Output is correct
10 Execution timed out 8029 ms 32268 KB Time limit exceeded
11 Correct 4258 ms 20128 KB Output is correct
12 Execution timed out 8093 ms 21060 KB Time limit exceeded
13 Execution timed out 8068 ms 21096 KB Time limit exceeded
14 Execution timed out 8067 ms 21744 KB Time limit exceeded
15 Execution timed out 8093 ms 24440 KB Time limit exceeded
16 Execution timed out 8084 ms 27568 KB Time limit exceeded
17 Execution timed out 8098 ms 28328 KB Time limit exceeded