Submission #833101

# Submission time Handle Problem Language Result Execution time Memory
833101 2023-08-22T00:52:21 Z Lobo Simurgh (IOI17_simurgh) C++17
0 / 100
2 ms 592 KB
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

const int maxn = 550;
const int maxm = maxn*maxn/2;

int n, m, h[maxn], mark[maxn], U[maxm], V[maxm];
pair<int,int> low[maxn];
vector<int> g[maxn], span, ins, outs;
int par[maxn], pari[maxn], is_span[maxm];
int in[maxm], out[maxm];
int queryspan;
int ds[maxn], dsz[maxn];

int find(int v) {
	if(v == ds[v]) return v;
	return ds[v] = find(ds[v]);
}

void join(int u, int v) {
	if(dsz[u] < dsz[v]) swap(u,v);
	dsz[u]+= dsz[v];
	ds[v] = u;
}

vector<int> construct(vector<int> edges) {
	vector<int> finaledges;

	for(int i = 0; i < n; i++) {
		ds[i] = i;
		dsz[i] = 1;
	}

	for(auto i : edges) {
		int u = find(U[i]);
		int v = find(V[i]);
		if(u != v) {
			join(u,v);
			finaledges.pb(i);
		}
	}

	return finaledges;
}

void dfslow(int u, int ant) {
	mark[u] = 1;
	low[u] = mp(h[u],-1);
	for(auto i : g[u]) {
		int v = U[i]+V[i]-u;
		if(v == ant) continue;

		if(!mark[v]) {
			h[v] = h[u]+1;
			par[v] = u;
			pari[v] = i;
			span.pb(i);
			is_span[i] = 1;
			dfslow(v,u);
			low[u] = min(low[u],low[v]);
		}
		else {
			low[u] = min(low[u],mp(h[v],i));
		}
	}
}

void dfs(int u, int ant) {
	for(auto i : g[u]) {
		int v = U[i]+V[i]-u;
		if(v == ant || is_span[i] == 0) continue;
		dfs(v,u);
	}

	if(u == 0 || in[pari[u]] || out[pari[u]]) return;
	
	if(low[u] == mp(h[u],-1)) {
		in[pari[u]] = 1;
		ins.pb(pari[u]);
	}
	else {
		int ilow = low[u].sc;
		int ulow = U[ilow];
		int vlow = V[ilow];
		if(h[ulow] > h[vlow]) swap(ulow,vlow);

		int v = vlow;
		vector<int> edges;
		while(v != ulow) {
			edges.pb(pari[v]);
			v = par[v];
		}

		int know = -1;
		for(auto i : edges) {
			if(in[i] || out[i]) {
				know = i;
			}
		}

		// cout << u << " " << ilow << " - " << count_common_roads(construct(span)) << endl;

		if(know == -1) {
			vector<pair<int,int>> cons;
			cons.pb(mp(queryspan,ilow));
			for(auto i : edges) {
				vector<int> doquery;
				for(auto j : span) {
					if(j != i) doquery.pb(j);
				}
				doquery.pb(ilow);
				cons.pb(mp(count_common_roads(construct(doquery)),i));
			}

			sort(all(cons));
			if(cons[0].fr == cons.back().fr) {
				// todo mundo out / 0
				out[ilow] = 1; outs.pb(ilow);
				for(auto i : edges) {
					out[i] = 1; outs.pb(i);
				}
			}
			else {
				for(auto X : cons) {
					int i = X.sc;
					if(X.fr < cons.back().fr) {
						// in / 1
						in[i] = 1; ins.pb(i);
					}
					else {
						// out / 0
						out[i] = 1; outs.pb(i);
					}
				}
			}
		}
		else {
			vector<pair<int,int>> cons;
			cons.pb(mp(queryspan,ilow));

			vector<int> doquery;
			for(auto i : edges) {
				if(i != pari[u]) {
					doquery.pb(i);
				}
			}
			doquery.pb(ilow);
			cons.pb(mp(count_common_roads(construct(doquery)),pari[u]));
			doquery.clear();

			for(auto i : edges) {
				if(i != know) {
					doquery.pb(i);
				}
			}
			doquery.pb(ilow);
			cons.pb(mp(count_common_roads(construct(doquery)),know));
			doquery.clear();

			if(in[know]) {
				if(cons[0].fr == cons[2].fr) {
					in[ilow] = 1; ins.pb(ilow);
				}
				else {
					out[ilow] = 1; outs.pb(ilow);
				}

				if(cons[1].fr == cons[2].fr) {
					in[pari[u]] = 1; ins.pb(pari[u]);
				}
				else {
					out[pari[u]] = 1; outs.pb(pari[u]);
				}
			}
			else {
				if(cons[0].fr == cons[2].fr) {
					out[ilow] = 1; outs.pb(ilow);
				}
				else {
					in[ilow] = 1; ins.pb(ilow);
				}

				if(cons[1].fr == cons[2].fr) {
					out[pari[u]] = 1; outs.pb(pari[u]);
				}
				else {
					in[pari[u]] = 1; ins.pb(pari[u]);
				}
			}
		}
	}
}

vector<int> find_roads(int N, std::vector<int> UU, std::vector<int> VV) {
	n = N;
	m = UU.size();
	for(int i = 0; i < m; i++) {
		U[i] = UU[i];
		V[i] = VV[i];
		g[U[i]].pb(i);
		g[V[i]].pb(i);
	}

	par[0] = -1;
	pari[0] = -1;
	dfslow(0,-1);
	queryspan = count_common_roads(construct(span));
	dfs(0,-1);

	for(int u = 0; u < n; u++) {
		int L = 0;
		while(L < g[u].size()) {
			int l = L;
			int r = (int) g[u].size()-1;
			int nx = -1;
			while(l <= r) {
				int mid = (l+r)>>1;
				vector<int> doquery;

				for(int i = 0; i <= mid; i++) doquery.pb(g[u][i]);
				for(auto i : span) doquery.pb(i);

				vector<int> used = construct(doquery);
				int should = 0;
				for(auto i : used) should+= in[i];

				if(count_common_roads(used) > should) {
					nx = mid;
					r = mid-1;
				}
				else {
					l = mid+1;
				}
			}
			if(nx == -1) break;
			in[g[u][nx]] = 1; ins.pb(g[u][nx]);
			L = nx+1;
		}
	}

	assert(ins.size() > n-1);
	return ins;

	for(auto i : span) {
		cout << i << " " << in[i] << " " << out[i] << endl;
	}
	return vector<int>{0};

}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:218:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |   while(L < g[u].size()) {
      |         ~~^~~~~~~~~~~~~
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:247:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  247 |  assert(ins.size() > n-1);
      |         ~~~~~~~~~~~^~~~~
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -