oj.uz

Submission #138042

# Submission time Handle Problem Language Result Execution time Memory
138042 2019-07-29T06:48:27 Z RockyB Highway Tolls (IOI18_highway) C++17
0 / 100
 34 ms 6956 KB 
// In The Name Of God

#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

#define f first
#define s second

#define pb push_back
#define pp pop_back

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define nl '\n'
#define ioi exit(0);

typedef long long ll;

const int MAX_N = (int)1e5 + 7;
const int INF = (int)1e9 + 7;
	

int n, m, A, B;
vector < pair <int, int > > g[MAX_N];

namespace Tree {
	// We suppose that S or T is 0
	int depth;
	ll min_len;
	int dep[MAX_N];

	vector <int> e;

	void dfs(int v = 0, int p = -1, int lvl = 0) {
		dep[v] = lvl;
		for (auto to : g[v]) {
			if (to.f != p) {
				dfs(to.f, v, lvl + 1);
				if (lvl + 1 == depth) {
					e.pb(to.s);
				}
			}
		}
	}
	int id(const vector <int> &x) {
		if (sz(x) == 1) return x[0];
		int mid = sz(x) / 2;

		vector <int> q(m, 0), sol;

		rep(i, 0, mid - 1) {
			q[x[i]] = 1;
			sol.pb(x[i]);
		}

		ll cur = ask(q);
		if (cur > min_len) return id(sol);

		vector <int> on;
		rep(i, mid, sz(x) - 1) on.pb(x[i]);
		return id(on);
	}
	void solve() {
		if (n != m + 1) return;

		{ 
			vector <int> q(m, 0);
			min_len = ask(q);
			depth = min_len / A;
		}

		int ed = id(e);
		rep(i, 0, n - 1) {
			for (auto it : g[i]) {
				if (it.s == ed) {
					if (dep[i] > dep[it.f]) answer(0, i);
					else answer(0, it.f);
					ioi
				}	
			}
		}
		assert(0);
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int _A, int _B) {
  n = N;
  m = sz(U);
  A = _A;
  B = _B;
  rep(i, 0, m - 1) {
  	g[V[i]].pb({U[i], i});
  	g[U[i]].pb({V[i], i});
  }
  // copy finished

  Tree :: solve();
  answer(0, N - 1);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2756 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3108 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 6956 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3120 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 3112 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 3128 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -