Submission #569750

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
569750	2022-05-27 17:36:27	erto	Regions (IOI09_regions)	C++17	100 / 100	3864 ms	80872 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>
typedef long long int ll;
#define INF (1e9 + 7)
#define INF2 (998244353)
#define N (ll)2e5 + 5
using namespace std;
//#define int ll
int n, g, h, t1, t2, cur = 1, q, R;
int d[N], st[N], en[N], par[N][20], r[N];
vector<int> v[N], sts[N], ens[N], r2[N];
map<int, int> m[N];
void dfs(int x, int p){
    st[x] = cur++;
    sts[r[x]].push_back(cur - 1);
    r2[r[x]].push_back(x);
    par[x][0] = p;
    for(int i = 1; i<=20; i++){
        par[x][i] = par[par[x][i - 1]][i - 1];
    }
    for(auto u : v[x]){
        if(u != p)dfs(u, x);
    }
    en[x] = cur++;
    ens[r[x]].push_back(cur - 1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:23:19: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
   23 |         par[x][i] = par[par[x][i - 1]][i - 1];
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:22:21: note: within this loop
   22 |     for(int i = 1; i<=20; i++){
      |                    ~^~~~

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