Submission #487294

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
4872942021-11-15 04:54:37JooBitaro’s Party (JOI18_bitaro)C++17
100 / 100
943 ms167648 KiB
#include <bits/stdc++.h>
#define DEBUG false
using namespace std;
const int N = 1e5+10, BS = 200, INF = 1e9;
using pi = pair<int,int>;
int n,m,Q, sz[N], dis[N][BS], node[N][BS], tv[BS], tn[BS];
vector<int> bl, G[N];
bool ban[N];
void preprocess(){
for(int u = 1; u <= n; u++){
if(sz[u] < BS){
dis[u][sz[u]] = 0;
node[u][sz[u]] = u;
sz[u]++;
}
for(int v : G[u]){ //propagate current max to its child
int i = 0, j = 0, k = 0; //perform alike merge sort
while(i < sz[u] and j < sz[v] and k < BS){
if(dis[u][i] + 1 > dis[v][j]){
if(!ban[node[u][i]]){
tv[k] = dis[u][i] + 1;
tn[k] = node[u][i];
ban[node[u][i]] = true;
k++;
}
i++;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...