oj.uz

Submission #559680

# Submission time Handle Problem Language Result Execution time Memory
559680 2022-05-10T11:49:53 Z nonsensenonsense1 Simurgh (IOI17_simurgh) C++17
0 / 100
 1 ms 212 KB 
#include "simurgh.h"
#include <cstdio>
#include <cstring>
#include <vector>

const int N = 500;
const int E = N * N;
std::vector<std::pair<int, int> > g[N];
int u[N], val[N];
bool know[E], ans[E];

std::vector<int> edg;
int it;
void dfs(int v) {
	u[v] = it;
	for (int i = 0; i < (int)g[v].size(); ++i) if (!u[g[v][i].first]) {
		edg.push_back(g[v][i].second);
		dfs(g[v][i].first);
	}
}

std::vector<int> find_roads(int n, std::vector<int> u_, std::vector<int> v_) {
	for (int i = 0; i < (int)u_.size(); ++i) {
		g[u_[i]].push_back(std::make_pair(v_[i], i));
		g[v_[i]].push_back(std::make_pair(u_[i], i));
	}
	for (int i = 0; i < n; ++i) {
		memset(u, 0, n << 2);
		u[i] = 1;
		it = 0;
		for (int j = 0; j < n; ++j) if (!u[j]) {
			++it;
			dfs(j);
		}
		for (int iit = 1; iit <= it; ++iit) {
			for (int j = 0;; ++j) if (u[g[i][j].first] == iit) {
				edg.push_back(g[i][j].second);
				break;
			}
		}
		for (int iit = 1; iit <= it; ++iit) {
			int fi = edg[edg.size() - g[i].size() + iit - 1];
			edg.erase(edg.end() - g[i].size() + iit - 1);
			int mn = ~(1 << 31);
			bool askonce = 0;
			for (int j = 0; j < (int)g[i].size(); ++j) if (u[g[i][j].first] == iit) {
				if (!know[g[i][j].second] || !askonce) {
					edg.push_back(g[i][j].second);
					val[j] = count_common_roads(edg);
					if (know[g[i][j].second]) {
						mn = val[j] - ans[g[i][j].second];
						askonce = 1;
					}
					mn = std::min(mn, val[j]);
					edg.pop_back();
				}
			}
			for (int j = 0; j < (int)g[i].size(); ++j) if (u[g[i][j].first] == iit && !know[g[i][j].second]) {
				know[g[i][j].second] = 1;
				ans[g[i][j].second] = val[j] != mn;
			}
			edg.insert(edg.end() - g[i].size() + iit, fi);
		}
		edg.clear();
	}
	std::vector<int> ret;
	for (int i = 0; i < (int)u_.size(); ++i) if (ans[i]) ret.push_back(i);
	return ret;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -