oj.uz

Submission #516204

# Submission time Handle Problem Language Result Execution time Memory
516204 2022-01-20T15:35:09 Z Yuisuyuno Regions (IOI09_regions) C++14
65 / 100
 8000 ms 27160 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();
            //cout << itr << ' ' << itl << '\n';
            ans += itr - itl;
        }
        cout << ans << '\n';
        cout.flush();
    }
}

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6088 KB Output is correct
2 Correct 3 ms 6088 KB Output is correct
3 Correct 5 ms 6192 KB Output is correct
4 Correct 6 ms 6216 KB Output is correct
5 Correct 9 ms 6216 KB Output is correct
6 Correct 23 ms 6216 KB Output is correct
7 Correct 30 ms 6216 KB Output is correct
8 Correct 37 ms 6344 KB Output is correct
9 Correct 45 ms 6728 KB Output is correct
10 Correct 86 ms 6856 KB Output is correct
11 Correct 123 ms 7376 KB Output is correct
12 Correct 119 ms 7880 KB Output is correct
13 Correct 197 ms 7904 KB Output is correct
14 Correct 279 ms 8620 KB Output is correct
15 Correct 249 ms 10816 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8060 ms 12144 KB Time limit exceeded
2 Execution timed out 8054 ms 11460 KB Time limit exceeded
3 Execution timed out 8086 ms 14004 KB Time limit exceeded
4 Correct 242 ms 8592 KB Output is correct
5 Correct 352 ms 9900 KB Output is correct
6 Correct 1333 ms 10056 KB Output is correct
7 Correct 1842 ms 11584 KB Output is correct
8 Correct 1251 ms 16164 KB Output is correct
9 Correct 2091 ms 19000 KB Output is correct
10 Correct 3968 ms 22592 KB Output is correct
11 Correct 4225 ms 20120 KB Output is correct
12 Correct 6359 ms 20792 KB Output is correct
13 Correct 6414 ms 20848 KB Output is correct
14 Execution timed out 8031 ms 21156 KB Time limit exceeded
15 Execution timed out 8079 ms 24260 KB Time limit exceeded
16 Execution timed out 8025 ms 27160 KB Time limit exceeded
17 Execution timed out 8076 ms 26944 KB Time limit exceeded