oj.uz

답안 #954773

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954773 2024-03-28T14:08:24 Z n1k 수천개의 섬 (IOI22_islands) C++17
9.1 / 100
 92 ms 13164 KB 
#include "islands.h"

#include <bits/stdc++.h>

using namespace std;

vector<vector<array<int, 2>>> g;
vector<map<int, int>> connected;
vector<int> color, par, nett;

int x, y;

bool dfs(int u, int p){
	par[u] = p;
	color[u] = 1;

	if(nett[u]){
		return true;
	}

	for(auto [v, e]:g[u]){
		if(v==p)
			continue;
		if(color[v]){
			x = v;
			y = u;
			return true;
		}
		if(dfs(v, u)){
			return true;
		}
	}
	return false;
}

std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
	g.assign(N, {});
	connected.assign(N, {});
	color.assign(N, {});
	par.assign(N, {});
	nett.assign(N, {});

	for(int i=0; i<M; i++){
		if(not connected[U[i]][V[i]]){
			g[U[i]].push_back({V[i], i});
		}

		connected[U[i]][V[i]]++;

		if(connected[U[i]][V[i]]>=2 and connected[V[i]][U[i]]>=1){
			nett[U[i]]=1;
		}
		if(connected[U[i]][V[i]]>=1 and connected[V[i]][U[i]]>=2){
			nett[V[i]]=1;
		}
	}
	if(connected[0].size()>=2){
		nett[0] = 1;
	}
	for(int i=1; i<N; i++){
		if(connected[i].size()>=3){
			nett[i]=1;
		}
	}

	return dfs(0, -1);
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
1.75 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 344 KB Output is partially correct
2 Correct 0 ms 348 KB Output is correct
3 Partially correct 1 ms 348 KB Output is partially correct
4 Partially correct 0 ms 344 KB Output is partially correct
5 Partially correct 1 ms 348 KB Output is partially correct
6 Partially correct 91 ms 11980 KB Output is partially correct

Subtask #3
7.35 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 604 KB Output is partially correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Partially correct 0 ms 344 KB Output is partially correct
5 Correct 1 ms 604 KB Output is correct
6 Partially correct 0 ms 424 KB Output is partially correct
7 Correct 1 ms 348 KB Output is correct
8 Partially correct 1 ms 348 KB Output is partially correct
9 Partially correct 0 ms 348 KB Output is partially correct
10 Partially correct 1 ms 604 KB Output is partially correct
11 Partially correct 0 ms 348 KB Output is partially correct
12 Partially correct 1 ms 604 KB Output is partially correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Partially correct 1 ms 348 KB Output is partially correct
16 Correct 1 ms 344 KB Output is correct
17 Partially correct 47 ms 8280 KB Output is partially correct
18 Partially correct 36 ms 7040 KB Output is partially correct
19 Correct 1 ms 348 KB Output is correct
20 Partially correct 1 ms 344 KB Output is partially correct
21 Partially correct 0 ms 344 KB Output is partially correct
22 Partially correct 0 ms 348 KB Output is partially correct
23 Partially correct 92 ms 13164 KB Output is partially correct

Subtask #4
0.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 2 ms 604 KB Output is partially correct
3 Partially correct 63 ms 3668 KB Output is partially correct
4 Partially correct 87 ms 10172 KB Output is partially correct
5 Partially correct 2 ms 604 KB Output is partially correct
6 Partially correct 2 ms 600 KB Output is partially correct
7 Partially correct 1 ms 348 KB Output is partially correct
8 Partially correct 0 ms 348 KB Output is partially correct
9 Partially correct 1 ms 348 KB Output is partially correct
10 Partially correct 1 ms 608 KB Output is partially correct
11 Incorrect 3 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 756 KB Output isn't correct
2 Halted 0 ms 0 KB -