oj.uz

Submission #516202

# Submission time Handle Problem Language Result Execution time Memory
516202 2022-01-20T15:30:09 Z Yuisuyuno Regions (IOI09_regions) C++14
0 / 100
 113 ms 27196 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];

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;
}

void proc()
{
    dfs(1);
    while (q--){
        int u, v;
        cin >> u >> v;
        int ans = 0;
        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();
            ans += itr - itl;
        }
        cout.flush();
        cout << ans << '\n';
    }
}

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

Compilation message

regions.cpp: In function 'void readfile()':
regions.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 6088 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 6088 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 6088 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 6216 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 6216 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 6216 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 6344 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 6728 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 6856 KB Time limit exceeded (wall clock)
11 Execution timed out 6 ms 7368 KB Time limit exceeded (wall clock)
12 Execution timed out 8 ms 7880 KB Time limit exceeded (wall clock)
13 Execution timed out 10 ms 7880 KB Time limit exceeded (wall clock)
14 Execution timed out 13 ms 8520 KB Time limit exceeded (wall clock)
15 Execution timed out 12 ms 10696 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 21 ms 12224 KB Time limit exceeded (wall clock)
2 Execution timed out 23 ms 11456 KB Time limit exceeded (wall clock)
3 Execution timed out 25 ms 14036 KB Time limit exceeded (wall clock)
4 Execution timed out 12 ms 8520 KB Time limit exceeded (wall clock)
5 Execution timed out 13 ms 9864 KB Time limit exceeded (wall clock)
6 Execution timed out 19 ms 10048 KB Time limit exceeded (wall clock)
7 Execution timed out 30 ms 11596 KB Time limit exceeded (wall clock)
8 Execution timed out 31 ms 16064 KB Time limit exceeded (wall clock)
9 Execution timed out 57 ms 18880 KB Time limit exceeded (wall clock)
10 Execution timed out 68 ms 22516 KB Time limit exceeded (wall clock)
11 Execution timed out 83 ms 20100 KB Time limit exceeded (wall clock)
12 Execution timed out 110 ms 20680 KB Time limit exceeded (wall clock)
13 Execution timed out 97 ms 20764 KB Time limit exceeded (wall clock)
14 Execution timed out 113 ms 21176 KB Time limit exceeded (wall clock)
15 Execution timed out 76 ms 24204 KB Time limit exceeded (wall clock)
16 Execution timed out 73 ms 27196 KB Time limit exceeded (wall clock)
17 Execution timed out 72 ms 26908 KB Time limit exceeded (wall clock)