Submission #501509

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
501509	2022-01-03 14:42:28	Joo	Regions (IOI09_regions)	C++17	65 / 100	8073 ms	46772 KiB

regions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10, BLOCK = 2e5+10, MR = 25010;
int n, R, Q, tin[N], tout[N], sz[N], re[N], cnt[MR], ti;
vector<int> ans[MR]; //stores answer for big regions(precompute)
vector<int> lis[MR], G[N], ch[N]; //lis[i] denotes a list of those whose region is i sorted by tin[i]
inline void add(int p, int u){
    ch[p].emplace_back(u);
    cnt[re[u]]++;
}
inline bool isbig(int r){
    return ((int)lis[r].size() > BLOCK);
}
inline bool isAnc(int p, int u){
    return (tin[p] <= tin[u] and tout[u] <= tout[p]);
}
void dfs1(int u){
    sz[u] = 1;
    lis[re[u]].emplace_back(u);
    tin[u] = ++ti;
    for(int v : G[u]) dfs1(v), sz[u] += sz[v];
    tout[u] = ti;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

regions.cpp: In function 'int getans(int, int)':
regions.cpp:65:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     while(b < lis[r1].size() or s < lis[r2].size()){
      |           ~~^~~~~~~~~~~~~~~~
regions.cpp:65:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     while(b < lis[r1].size() or s < lis[r2].size()){
      |                                 ~~^~~~~~~~~~~~~~~~
regions.cpp:66:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if((b < lis[r1].size()) and (s == lis[r2].size() or tin[lis[r1][b]] < tin[lis[r2][s]])){
      |             ~~^~~~~~~~~~~~~~~~
regions.cpp:66:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if((b < lis[r1].size()) and (s == lis[r2].size() or tin[lis[r1][b]] < tin[lis[r2][s]])){
      |                                      ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 50 / 85