oj.uz

답안 #435023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
435023 2021-06-22T20:15:42 Z Arturgo 열쇠 (IOI21_keys) C++17
9 / 100
 392 ms 57436 KB 
#include <vector>
#include <iostream>
#include <set>
using namespace std;

int nbPieces, nbRoutes;
vector<int> ordre;
vector<int> parents[300 * 1000];

int curPasse;
int derPasse[300 * 1000];

int curDate;
int date[300 * 1000];

void dfs(int piece) {
	if(derPasse[piece] == curPasse)
		return;
	derPasse[piece] = curPasse;
	
	for(int parent : parents[piece])
		dfs(parent);
	
	ordre.push_back(piece);
}

bool cles[300 * 1000];
vector<int> sommetsVus[300 * 1000];
vector<int> aNettoyer;

vector<int> c, r;

vector<pair<int, int>> voisins[300 * 1000];

int minNbVus = 1000 * 1000 * 1000;
vector<int> reponse;

void explore(int piece) {
	vector<int> sommetsOks;
	sommetsOks.push_back(piece);
	
	bool accedeAutre = false;
	vector<int> vus;
	
	curDate++;
	
	while(!sommetsOks.empty()) {
		int sommet = sommetsOks.back();
		sommetsOks.pop_back();
		
		if(date[sommet] == curDate)
			continue;
		if(date[sommet] != 0) {
			accedeAutre = true;
			continue;
		}
		
		vus.push_back(sommet);
		date[sommet] = curDate;
		
		cles[r[sommet]] = true;
		aNettoyer.push_back(r[sommet]);
		
		for(int sommet : sommetsVus[r[sommet]]) {
			sommetsOks.push_back(sommet);
		}
		sommetsVus[r[sommet]].clear();
		
		for(pair<int, int> voisin : voisins[sommet]) {
			if(cles[voisin.second])
				sommetsOks.push_back(voisin.first);
			else {
				sommetsVus[voisin.second].push_back(voisin.first);
				aNettoyer.push_back(voisin.second);
			}
		}
	}
	
	while(!aNettoyer.empty()) {
		int pos = aNettoyer.back();
		aNettoyer.pop_back();
		sommetsVus[pos].clear();
		cles[pos] = false;
	}
	
	if(accedeAutre)
		return;
	
	if(vus.size() < minNbVus) {
		minNbVus = vus.size();
		reponse.clear();
	}
	if(vus.size() == minNbVus) {
		for(int vu : vus) {
			reponse.push_back(vu);
		}
	}
}

vector<int> find_reachable(vector<int> _r, vector<int> u, vector<int> v, vector<int> _c) {
	c = _c;
	r = _r;
	int nbPieces = r.size();
	int nbRoutes = u.size();
	
	for(int iRoute = 0;iRoute < nbRoutes;iRoute++) {
		if(c[iRoute] == r[u[iRoute]])
			parents[v[iRoute]].push_back(u[iRoute]);
		if(c[iRoute] == r[v[iRoute]])
			parents[u[iRoute]].push_back(v[iRoute]);
		voisins[u[iRoute]].push_back({v[iRoute], c[iRoute]});
		voisins[v[iRoute]].push_back({u[iRoute], c[iRoute]});
	}
	
	curPasse++;
	for(int iPiece = 0;iPiece < nbPieces;iPiece++) {
		dfs(iPiece);
	}
	
	while(!ordre.empty()) {
		int piece = ordre.back();
		ordre.pop_back();
		explore(piece);
	}
	
	vector<int> ans(nbPieces, 0);
	
	for(int x : reponse)
		ans[x] = 1;
	
	return ans;
}

Compilation message

keys.cpp: In function 'void explore(int)':
keys.cpp:89:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |  if(vus.size() < minNbVus) {
      |     ~~~~~~~~~~~^~~~~~~~~~
keys.cpp:93:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |  if(vus.size() == minNbVus) {
      |     ~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 21448 KB Output is correct
2 Correct 16 ms 21388 KB Output is correct
3 Correct 16 ms 21324 KB Output is correct
4 Correct 14 ms 21352 KB Output is correct
5 Correct 15 ms 21324 KB Output is correct
6 Correct 14 ms 21448 KB Output is correct
7 Correct 14 ms 21352 KB Output is correct
8 Correct 14 ms 21452 KB Output is correct
9 Correct 14 ms 21472 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 21448 KB Output is correct
2 Correct 16 ms 21388 KB Output is correct
3 Correct 16 ms 21324 KB Output is correct
4 Correct 14 ms 21352 KB Output is correct
5 Correct 15 ms 21324 KB Output is correct
6 Correct 14 ms 21448 KB Output is correct
7 Correct 14 ms 21352 KB Output is correct
8 Correct 14 ms 21452 KB Output is correct
9 Correct 14 ms 21472 KB Output is correct
10 Correct 14 ms 21468 KB Output is correct
11 Correct 13 ms 21452 KB Output is correct
12 Correct 16 ms 21452 KB Output is correct
13 Correct 14 ms 21376 KB Output is correct
14 Correct 14 ms 21324 KB Output is correct
15 Correct 14 ms 21468 KB Output is correct
16 Correct 14 ms 21408 KB Output is correct
17 Incorrect 15 ms 21444 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 21448 KB Output is correct
2 Correct 16 ms 21388 KB Output is correct
3 Correct 16 ms 21324 KB Output is correct
4 Correct 14 ms 21352 KB Output is correct
5 Correct 15 ms 21324 KB Output is correct
6 Correct 14 ms 21448 KB Output is correct
7 Correct 14 ms 21352 KB Output is correct
8 Correct 14 ms 21452 KB Output is correct
9 Correct 14 ms 21472 KB Output is correct
10 Correct 14 ms 21468 KB Output is correct
11 Correct 13 ms 21452 KB Output is correct
12 Correct 16 ms 21452 KB Output is correct
13 Correct 14 ms 21376 KB Output is correct
14 Correct 14 ms 21324 KB Output is correct
15 Correct 14 ms 21468 KB Output is correct
16 Correct 14 ms 21408 KB Output is correct
17 Incorrect 15 ms 21444 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 21448 KB Output is correct
2 Correct 16 ms 21388 KB Output is correct
3 Correct 16 ms 21324 KB Output is correct
4 Correct 14 ms 21352 KB Output is correct
5 Correct 15 ms 21324 KB Output is correct
6 Correct 14 ms 21448 KB Output is correct
7 Correct 14 ms 21352 KB Output is correct
8 Correct 14 ms 21452 KB Output is correct
9 Correct 14 ms 21472 KB Output is correct
10 Correct 292 ms 47140 KB Output is correct
11 Correct 392 ms 57436 KB Output is correct
12 Incorrect 85 ms 28472 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 21448 KB Output is correct
2 Correct 16 ms 21388 KB Output is correct
3 Correct 16 ms 21324 KB Output is correct
4 Correct 14 ms 21352 KB Output is correct
5 Correct 15 ms 21324 KB Output is correct
6 Correct 14 ms 21448 KB Output is correct
7 Correct 14 ms 21352 KB Output is correct
8 Correct 14 ms 21452 KB Output is correct
9 Correct 14 ms 21472 KB Output is correct
10 Correct 14 ms 21468 KB Output is correct
11 Correct 13 ms 21452 KB Output is correct
12 Correct 16 ms 21452 KB Output is correct
13 Correct 14 ms 21376 KB Output is correct
14 Correct 14 ms 21324 KB Output is correct
15 Correct 14 ms 21468 KB Output is correct
16 Correct 14 ms 21408 KB Output is correct
17 Incorrect 15 ms 21444 KB Output isn't correct
18 Halted 0 ms 0 KB -