oj.uz

Submission #833113

# Submission time Handle Problem Language Result Execution time Memory
833113 2023-08-22T01:12:24 Z Lobo Simurgh (IOI17_simurgh) C++17
19 / 100
 148 ms 5476 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);
		}
	}
assert((int) finaledges.size()==n-1);
 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);
	assert(count_common_roads(ins) == 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:219:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |   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:3:
simurgh.cpp:248:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  248 |  assert(ins.size() >= n-1);
      |         ~~~~~~~~~~~^~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 0 ms 340 KB correct
4 Runtime error 1 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 0 ms 340 KB correct
4 Runtime error 1 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 0 ms 340 KB correct
4 Runtime error 1 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 89 ms 3620 KB correct
4 Correct 139 ms 5476 KB correct
5 Correct 139 ms 5220 KB correct
6 Correct 136 ms 5068 KB correct
7 Correct 130 ms 5160 KB correct
8 Correct 131 ms 5144 KB correct
9 Correct 140 ms 5180 KB correct
10 Correct 137 ms 5136 KB correct
11 Correct 148 ms 5124 KB correct
12 Correct 137 ms 5196 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 137 ms 5228 KB correct
15 Correct 143 ms 5132 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 1 ms 340 KB correct
3 Correct 0 ms 340 KB correct
4 Runtime error 1 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -