oj.uz

답안 #596132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
596132 2022-07-14T12:04:56 Z mohammad_kilani 게임 (APIO22_game) C++17
2 / 100
 1 ms 256 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

int n , k;

vector< int > mx , mn , l , r;

vector< vector< int > > g , g2;

bool fixNode(int node){
	if(mx[node] >= mn[node])
		return false;
	int mid;
	bool good = false;
	while(l[node] < r[node]){
		mid = (l[node] + r[node]) / 2;
		if(mn[node] <= mid){
			r[node] = mid;
			good = true;
		}
		else if(mx[node] > mid){
			l[node] = mid + 1;
			good = true;
		}
		else
			break;
	}
	return good;
}

void init(int n, int k) {
	::n = n;
	::k = k;
	mx.resize(n , 0);
	mn.resize(n , k + 1);
	l.resize(n , 0);
	r.resize(n , k + 1);

	for(int i = 0 ;i < k;i++){
		mn[i] = mx[i] = i + 1;
	}
	g.resize(n);
	g2.resize(n);
}

void DFSMax(int node){
	for(int i = 0 ;i < (int)g[node].size();i++){
		if(g[node][i] < k){
			mn[node] = min(mn[node] , g[node][i] + 1);
			continue;
		}
		mx[g[node][i]] = max(mx[g[node][i]] , mx[node]);
		if(fixNode(g[node][i])){
			DFSMax(g[node][i]);
			mn[node] = min(mn[node] , mn[g[node][i]]);
		}
	}
	fixNode(node);
}

void DFSMin(int node){
	for(int i = 0 ;i < (int)g2[node].size();i++){
		if(g2[node][i] < k){
			mx[node] = max(mx[node] , g2[node][i] + 1);
			continue;
		}
		mn[g2[node][i]] = min(mn[g2[node][i]] , mn[node]);
		if(fixNode(g2[node][i])){
			DFSMin(g2[node][i]);
			mx[node] = max(mx[node] , mx[g2[node][i]]);
		}
	}
	fixNode(node);
}

int add_teleporter(int u, int v) {
	if(u < k && v < k){
		if(u >= v)
			return 1;
		return 0;
	}
	g[u].push_back(v);
	g2[v].push_back(u);


	//fix max
	if(v >= k){
		mx[v] = max(mx[v] , mx[u]);
		if(fixNode(v))
			DFSMax(v);

		if(mx[v] >= mn[v])
			return 1;
	}
	//fix min
	if(u >= k){
		mn[u] = min(mn[u] , mn[v]);
		if(fixNode(u))
			DFSMin(u);
		if(mx[u] >= mn[u])
			return 1;
	}
 	return 0;
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Incorrect 0 ms 208 KB Wrong Answer[1]
15 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Incorrect 0 ms 208 KB Wrong Answer[1]
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Incorrect 0 ms 208 KB Wrong Answer[1]
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Incorrect 0 ms 208 KB Wrong Answer[1]
15 Halted 0 ms 0 KB -