oj.uz

Submission #586265

# Submission time Handle Problem Language Result Execution time Memory
586265 2022-06-30T05:50:27 Z jamezzz Game (APIO22_game) C++17
0 / 100
 8 ms 14360 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define maxn 300005

int n,k,low[maxn],high[maxn];
vector<int> AL[maxn],AL2[maxn];

void dfs(int u,int x){
	for(int v:AL[u]){
		if(high[v]<x){
			high[v]=x;
			dfs(v,x);
		}
	}
}

void dfs2(int u,int x){
	for(int v:AL2[u]){
		if(x<low[v]){
			low[v]=x;
			dfs2(v,x);
		}
	}
}

void init(int _n,int _k){
	n=_n;k=_k;
	for(int i=0;i<n;++i){
		high[i]=-1;
		low[i]=k;
	}
	for(int i=0;i<k-1;++i){
		AL[i].pb(i+1);
		AL2[i+1].pb(i);
	}
}

int add_teleporter(int u,int v){
	//if(v<=u&&u<k)return 1;
	
	if(v<k)low[v]=min(low[v],v);
	if(u<k)high[u]=max(high[u],u);
	AL[u].pb(v);
	AL2[v].pb(u);
	dfs(u,high[u]);
	dfs2(v,low[v]);
	
	/*
	printf("low: ");
	for(int i=0;i<n;++i)printf("%d ",low[i]);
	printf("\n");
	printf("high: ");
	for(int i=0;i<n;++i)printf("%d ",high[i]);
	printf("\n");
	*/
	
	for(int u=0;u<n;++u){
		if(low[u]<=high[u])return 1;
	}
	return 0;
}

Subtask #1
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14360 KB Output is correct
2 Incorrect 8 ms 14288 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14360 KB Output is correct
2 Incorrect 8 ms 14288 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14360 KB Output is correct
2 Incorrect 8 ms 14288 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14360 KB Output is correct
2 Incorrect 8 ms 14288 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14360 KB Output is correct
2 Incorrect 8 ms 14288 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -