Submission #254017

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
254017	2020-07-29 09:10:50	maximath_1	Tax Evasion (LMIO19_mokesciai)	C++11	100 / 100	231 ms	47580 KiB

mokesciai

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
/*
  * LMIO 2019 Tax Evasion
  * Main Idea : Euler tour, binary search the answer
  * If there's a coin at depth d, it can only climb to
  * floor((d - 1) / 2), as Just will get caught afterwards
  * So we can build an euler tour, coin X can only stay at
  * a range L to R
  * Binary search the answer: if a is a candidate answer, 
  * all coins should have depth at least a - 1
  * Check if >= a possible using greedy
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, timer;
int par[18][200005], depth[200005], lf[200005], rg[200005];
bool is_coin[200005];
vector<int> adj[200005], que[200005], order;
void euler_tour(int nw){
  order.push_back(nw);
  lf[nw] = timer ++;
  for(int nx : adj[nw])
    euler_tour(nx);
  rg[nw] = timer;
}
int anc(int nw, int dp){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 39 / 39
• Subtask 4: 29 / 29