oj.uz

Submission #517056

# Submission time Handle Problem Language Result Execution time Memory
517056 2022-01-22T12:58:10 Z Yuisuyuno Regions (IOI09_regions) C++14
0 / 100
 8000 ms 31612 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';
            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';
    }
}

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

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 6200 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 6088 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 6192 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 6216 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 6196 KB Time limit exceeded (wall clock)
6 Execution timed out 5 ms 6208 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 6216 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 6336 KB Time limit exceeded (wall clock)
9 Execution timed out 5 ms 6704 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 6960 KB Time limit exceeded (wall clock)
11 Execution timed out 10 ms 7348 KB Time limit exceeded (wall clock)
12 Execution timed out 12 ms 7880 KB Time limit exceeded (wall clock)
13 Execution timed out 10 ms 7852 KB Time limit exceeded (wall clock)
14 Execution timed out 12 ms 8536 KB Time limit exceeded (wall clock)
15 Execution timed out 14 ms 10688 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6070 ms 12420 KB Time limit exceeded (wall clock)
2 Execution timed out 5804 ms 11764 KB Time limit exceeded (wall clock)
3 Execution timed out 8082 ms 14092 KB Time limit exceeded
4 Execution timed out 17 ms 8520 KB Time limit exceeded (wall clock)
5 Execution timed out 14 ms 9800 KB Time limit exceeded (wall clock)
6 Execution timed out 3656 ms 13736 KB Time limit exceeded (wall clock)
7 Execution timed out 1201 ms 13140 KB Time limit exceeded (wall clock)
8 Execution timed out 8098 ms 23492 KB Time limit exceeded
9 Execution timed out 57 ms 18972 KB Time limit exceeded (wall clock)
10 Execution timed out 8073 ms 31612 KB Time limit exceeded
11 Execution timed out 76 ms 20068 KB Time limit exceeded (wall clock)
12 Execution timed out 8080 ms 21056 KB Time limit exceeded
13 Execution timed out 8087 ms 21088 KB Time limit exceeded
14 Execution timed out 8080 ms 21648 KB Time limit exceeded
15 Execution timed out 8048 ms 24384 KB Time limit exceeded
16 Execution timed out 8058 ms 27568 KB Time limit exceeded
17 Execution timed out 8066 ms 28288 KB Time limit exceeded