oj.uz

Submission #435022

# Submission time Handle Problem Language Result Execution time Memory
435022 2021-06-22T20:06:57 Z Arturgo Keys (IOI21_keys) C++17
9 / 100
 369 ms 47780 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[c[sommet]]) {
			sommetsOks.push_back(sommet);
		}
		sommetsVus[c[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

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21420 KB Output is correct
2 Correct 14 ms 21436 KB Output is correct
3 Correct 14 ms 21384 KB Output is correct
4 Correct 14 ms 21408 KB Output is correct
5 Correct 14 ms 21448 KB Output is correct
6 Correct 14 ms 21324 KB Output is correct
7 Correct 14 ms 21384 KB Output is correct
8 Correct 16 ms 21452 KB Output is correct
9 Correct 14 ms 21452 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21420 KB Output is correct
2 Correct 14 ms 21436 KB Output is correct
3 Correct 14 ms 21384 KB Output is correct
4 Correct 14 ms 21408 KB Output is correct
5 Correct 14 ms 21448 KB Output is correct
6 Correct 14 ms 21324 KB Output is correct
7 Correct 14 ms 21384 KB Output is correct
8 Correct 16 ms 21452 KB Output is correct
9 Correct 14 ms 21452 KB Output is correct
10 Correct 14 ms 21460 KB Output is correct
11 Correct 14 ms 21372 KB Output is correct
12 Correct 16 ms 21580 KB Output is correct
13 Correct 15 ms 21324 KB Output is correct
14 Runtime error 39 ms 43204 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21420 KB Output is correct
2 Correct 14 ms 21436 KB Output is correct
3 Correct 14 ms 21384 KB Output is correct
4 Correct 14 ms 21408 KB Output is correct
5 Correct 14 ms 21448 KB Output is correct
6 Correct 14 ms 21324 KB Output is correct
7 Correct 14 ms 21384 KB Output is correct
8 Correct 16 ms 21452 KB Output is correct
9 Correct 14 ms 21452 KB Output is correct
10 Correct 14 ms 21460 KB Output is correct
11 Correct 14 ms 21372 KB Output is correct
12 Correct 16 ms 21580 KB Output is correct
13 Correct 15 ms 21324 KB Output is correct
14 Runtime error 39 ms 43204 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21420 KB Output is correct
2 Correct 14 ms 21436 KB Output is correct
3 Correct 14 ms 21384 KB Output is correct
4 Correct 14 ms 21408 KB Output is correct
5 Correct 14 ms 21448 KB Output is correct
6 Correct 14 ms 21324 KB Output is correct
7 Correct 14 ms 21384 KB Output is correct
8 Correct 16 ms 21452 KB Output is correct
9 Correct 14 ms 21452 KB Output is correct
10 Incorrect 369 ms 47780 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21420 KB Output is correct
2 Correct 14 ms 21436 KB Output is correct
3 Correct 14 ms 21384 KB Output is correct
4 Correct 14 ms 21408 KB Output is correct
5 Correct 14 ms 21448 KB Output is correct
6 Correct 14 ms 21324 KB Output is correct
7 Correct 14 ms 21384 KB Output is correct
8 Correct 16 ms 21452 KB Output is correct
9 Correct 14 ms 21452 KB Output is correct
10 Correct 14 ms 21460 KB Output is correct
11 Correct 14 ms 21372 KB Output is correct
12 Correct 16 ms 21580 KB Output is correct
13 Correct 15 ms 21324 KB Output is correct
14 Runtime error 39 ms 43204 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -