oj.uz

답안 #1028821

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1028821 2024-07-20T09:12:02 Z DorostWef Simurgh (IOI17_simurgh) C++17
0 / 100
 1 ms 464 KB 
#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;
typedef pair <int, int> pii;
#define F first
#define S second
const int N = 506, M = N * N;
set <int> st;
vector <pii> g[N];
bool vis[N];
int h[N], par[N];
int a[M], b[M];
int w[M];
vector <int> tree;
int p[N], sz[N];
int d[N];
int nn;
bool ff[M];

int get_par (int v) {
	if (p[v] == v)
		return v;
	return p[v] = get_par (p[v]);
}

bool merge(int u, int v) {
	u = get_par (u);
	v = get_par (v);
	if (u == v)
		return false;
	if (sz[u] > sz[v])
		swap (u, v);
	p[u] = v;
	return true;
}

void clear() {
	for (int i = 0; i < N; i++) {
		p[i] = i;
		sz[i] = 1;
	}
}

int askt () {
	vector <int> wef;
	for (int x : st)
		wef.push_back(x);
	return count_common_roads(wef);
}

void dfs (int v) {
	vis[v] = true;
	for (pii p : g[v]) {
		int u = p.F;
		if (!vis[u]) {
			h[u] = h[v] + 1;
			par[u] = p.S;
			dfs (u);
			tree.push_back (p.S);
			st.insert (p.S);
		}
	}
}

int askj (vector <int> wef) {
	clear();
	for (int i : wef) {
		assert (merge (a[i], b[i]));
	}
	int k = 0;
	for (int i : tree) {
		if (merge (a[i], b[i])) {
			wef.push_back (i);
			k += w[i];
		}
	}
	assert (wef.size() == nn - 1);
	int wefwef = count_common_roads (wef) - k;
	return wefwef;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	nn = n;
	int m = (int)u.size();
	for (int i = 0; i < m; i++) {
		w[i] = -1;
		a[i] = u[i];
		b[i] = v[i];
		g[a[i]].push_back(make_pair (b[i], i));
		g[b[i]].push_back(make_pair (a[i], i));
	}
	dfs (0);
	int k = askt();
	for (int i = 0; i < m; i++) {
		if (abs (h[a[i]] - h[b[i]]) >= 2) {
			if (h[a[i]] < h[b[i]])
				swap (a[i], b[i]);
			vector <int> alo;
			int vv = a[i];
			bool f = false;
			int h = -1;
			while (vv != b[i]) {
				if (w[par[vv]] == -1)
					f = true;
				if (w[par[vv]] != -1) 
					h = par[vv];
				alo.push_back (par[vv]);
				vv = a[par[vv]] ^ b[par[vv]] ^ vv;
			}
			if (!f)
				continue;
			if (h != -1) {
				st.insert(i);
				st.erase (vv);
				int o = askt();
				o = o - (k - w[vv]);
				st.insert (vv);
				for (int few : alo) {
					if (w[few] == -1) {
						st.erase (few);
						w[few] = k - (askt() - o);
						st.insert (few);
					}
				}
				st.erase(i);
			} else {
				st.insert (i);
				int mx = k;
				vector <int> what;
				for (int few : alo) {
					st.erase (few);
					int wef = askt();
					mx = max (mx, wef);
					what.push_back(wef);
					st.insert (few);
				}
				st.erase (i);
				for (int j = 0; j < (int)alo.size(); j++) {
					w[alo[j]] = mx - what[j];
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		vector <int> adj;
		for (pair <int, int> p : g[i])
			adj.push_back (p.S);
		d[i] = askj (adj);
	}
	vector <int> ans;
	for (int i = 0; i < n - 1; i++) {
		int x = -1;
		for (int j = 0; j < n; j++) {
			if (d[j] == 1) {
				x = j;
			}
		}
		assert (x != -1);
		vector <int> adj;
		for (pair <int, int> p : g[x]) {
			if (!ff[p.S]) 
				adj.push_back (p.S);
		}
		int l = -1, r = (int)adj.size() - 1;
		while (r - l > 1) {
			int mid = (l + r) >> 1;
			vector <int> wef;
			for (int j = 0; j <= mid; j++) {
				wef.push_back(adj[j]);
			}
			if (askj(wef) == 1) {
				r = mid;
			} else {
				l = mid;
			}
		}
		ff[adj[r]] = true;
		ans.push_back (adj[r]);
		d[a[adj[r]]]--;
		d[b[adj[r]]]--;
	}
	return ans;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp: In function 'int askj(std::vector<int>)':
simurgh.cpp:78:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |  assert (wef.size() == nn - 1);
      |          ~~~~~~~~~~~^~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB correct
2 Incorrect 0 ms 348 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB correct
2 Incorrect 0 ms 348 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB correct
2 Incorrect 0 ms 348 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB correct
2 Incorrect 0 ms 464 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB correct
2 Incorrect 0 ms 348 KB WA in grader: NO
3 Halted 0 ms 0 KB -