oj.uz

Submission #138044

# Submission time Handle Problem Language Result Execution time Memory
138044 2019-07-29T06:54:39 Z RockyB Highway Tolls (IOI18_highway) C++17
12 / 100
 232 ms 12520 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]);
		}

		// cerr << sz(x) << endl;
		assert(sz(sol));

		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;
		}
		dfs();
		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);
					return;
				}	
			}
		}
		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();
  return;
  answer(0, N - 1);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2676 KB Output is correct
3 Correct 4 ms 2756 KB Output is correct
4 Correct 4 ms 2752 KB Output is correct
5 Correct 4 ms 2552 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2676 KB Output is correct
9 Correct 4 ms 2552 KB Output is correct
10 Correct 4 ms 2668 KB Output is correct
11 Correct 4 ms 2668 KB Output is correct
12 Correct 4 ms 2680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2728 KB Output is correct
2 Correct 23 ms 3636 KB Output is correct
3 Correct 151 ms 12460 KB Output is correct
4 Correct 150 ms 12420 KB Output is correct
5 Correct 157 ms 12460 KB Output is correct
6 Correct 161 ms 11648 KB Output is correct
7 Correct 127 ms 12476 KB Output is correct
8 Correct 164 ms 12520 KB Output is correct
9 Correct 114 ms 11260 KB Output is correct
10 Correct 195 ms 12452 KB Output is correct
11 Correct 148 ms 10024 KB Output is correct
12 Correct 164 ms 10316 KB Output is correct
13 Correct 169 ms 10068 KB Output is correct
14 Correct 232 ms 9404 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3112 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 3132 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -