oj.uz

Submission #283909

# Submission time Handle Problem Language Result Execution time Memory
283909 2020-08-26T09:17:18 Z balbit Simurgh (IOI17_simurgh) C++14
0 / 100
 192 ms 3712 KB 
#include <bits/stdc++.h>
#ifndef BALBIT
#include "simurgh.h"
#endif
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
 
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
 
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template <typename T> void _do(T && x) {cerr<<x<<endl;}
template <typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#endif
const int maxn = 503;
 
#ifdef BALBIT
int count_common_roads(vector<int> x){
	for (int y : x) cout<<y<<" "; 
	cout<<endl;
	int r; cin>>r; return r;
 
}
 
#endif
 
vector<pii> g[maxn];
int par[maxn];
int find(int x){return x==par[x]?x:par[x]=find(par[x]);}
bool fun[maxn];
vector<int> spn(vector<int> a){
	memset(fun, 0, sizeof fun);
	for (int x : a) par[x] = x, fun[x] = 1;
	vector<int>re;
	for (int x : a) {
		for (pii u : g[x]) {
			if (fun[u.f] && find(u.f)!=find(x)) {
				par[find(u.f)]=find(x);
				re.pb(u.s);
			}
		}
	}
	assert(SZ(re) == SZ(a)-1);
	return re;
}
 
vector<int> find_roads(int n, vector<int> UU, vector<int> VV) {
	int m = SZ(UU);
	vector<int> re;
	for (int i = 0; i<m; ++i) {
		g[UU[i]].pb({VV[i], i});
		g[VV[i]].pb({UU[i], i});
	}
	vector<int> isok(m);
	for (int i = 0; i<n-1; ++i) {
		vector<int> tmp, tmp2;
		for (int j = 0; j<n; ++j) {
			(j==i?tmp:tmp2).pb(j);
		}
		vector<int> T = spn(tmp);
		vector<int> T2 = spn(tmp2);
		for (int x : T2) T.pb(x);
		int IT = 0;
		vector<int> vl;
		for (pii u : g[i]){
			if(u.f != i) {
				vector<int> tt = T; tt.pb(u.s);
				vl.pb(count_common_roads(tt));
			}
		}
		int bar = *max_element(ALL(vl));
 
		for (pii u : g[i]){
			if(u.f != i) {
				if (vl[IT] == bar && !isok[u.s]) {
					re.pb(u.s); isok[u.s ] = 1;
				}
				++IT;
			}
		}
	}

	return re;
}
 
#ifdef BALBIT
signed main(){
	IOS();
 
	vector<int> hmm = find_roads(4, {0, 0, 0, 1, 1, 2}, {1, 2, 3, 2, 3, 3});
	for (int x : hmm) bug(x);
}
#endif

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 0 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 0 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 0 ms 384 KB correct
9 Runtime error 1 ms 512 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 0 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 0 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 0 ms 384 KB correct
9 Runtime error 1 ms 512 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 0 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 0 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 0 ms 384 KB correct
9 Runtime error 1 ms 512 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB correct
2 Correct 1 ms 384 KB correct
3 Incorrect 192 ms 3712 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 0 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 0 ms 384 KB correct
5 Correct 1 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 0 ms 384 KB correct
9 Runtime error 1 ms 512 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -