Submission #669999

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
669999	2022-12-07 17:55:09	Iliya	Regions (IOI09_regions)	C++17	100 / 100	5426 ms	84272 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
/*
 Lemme check my list of powers and weaknesses: 
 ability to do anything, but only whenever I want.
*/
 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int N = 2e5 + 10, R = 3e4, Q = 2e5 + 10, SQ = 499;
int n, r, q, Time, H[N], P[N], St[N], Ft[N], ID[R], cnt[N], Ans[SQ][R];
vector<int> Adj[N], Reg[R], Home[R];
 
void PreDFS(int v){
  St[v] = ++Time;
  Reg[H[v]].push_back(Time);
  for(int u : Adj[v])
    PreDFS(u);
  Ft[v] = Time;
}
 
void DFS(int v){
  if((int) Home[H[v]].size() >= SQ) cnt[ID[H[v]]]++;
  for(int u : Adj[v]){
    for(int i = 1; i < SQ; i++)
      Ans[i][H[u]] += cnt[i];
    DFS(u);
  }
  if((int) Home[H[v]].size() >= SQ) cnt[ID[H[v]]]--;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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