oj.uz

Submission #517058

# Submission time Handle Problem Language Result Execution time Memory
517058 2022-01-22T13:00:25 Z Yuisuyuno Regions (IOI09_regions) C++14
35 / 100
 8000 ms 32140 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()==0) continue;
        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]){
            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 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 4 ms 6252 KB Output is correct
2 Correct 3 ms 6144 KB Output is correct
3 Correct 5 ms 6216 KB Output is correct
4 Correct 10 ms 6216 KB Output is correct
5 Correct 13 ms 6216 KB Output is correct
6 Correct 11 ms 6216 KB Output is correct
7 Correct 39 ms 6216 KB Output is correct
8 Correct 37 ms 6344 KB Output is correct
9 Correct 80 ms 6784 KB Output is correct
10 Correct 73 ms 6984 KB Output is correct
11 Correct 94 ms 7380 KB Output is correct
12 Correct 190 ms 7840 KB Output is correct
13 Correct 213 ms 7940 KB Output is correct
14 Correct 312 ms 8520 KB Output is correct
15 Correct 295 ms 10716 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8071 ms 12496 KB Time limit exceeded
2 Incorrect 7429 ms 11672 KB Output isn't correct
3 Execution timed out 8093 ms 14196 KB Time limit exceeded
4 Correct 167 ms 8600 KB Output is correct
5 Correct 330 ms 9908 KB Output is correct
6 Incorrect 4119 ms 13684 KB Output isn't correct
7 Incorrect 2706 ms 13092 KB Output isn't correct
8 Execution timed out 8021 ms 23616 KB Time limit exceeded
9 Correct 2533 ms 19008 KB Output is correct
10 Execution timed out 8098 ms 32140 KB Time limit exceeded
11 Correct 4803 ms 20132 KB Output is correct
12 Execution timed out 8079 ms 21064 KB Time limit exceeded
13 Execution timed out 8061 ms 21092 KB Time limit exceeded
14 Execution timed out 8032 ms 21688 KB Time limit exceeded
15 Execution timed out 8010 ms 24452 KB Time limit exceeded
16 Execution timed out 8055 ms 27564 KB Time limit exceeded
17 Execution timed out 8089 ms 28220 KB Time limit exceeded