oj.uz

Submission #858842

# Submission time Handle Problem Language Result Execution time Memory
858842 2023-10-09T09:01:28 Z waldi Highway Tolls (IOI18_highway) C++17
51 / 100
 115 ms 14164 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

void find_pair(int n, vector<int> u, vector<int> v, int a_int, int b_int){
	int m = u.size();
	ll a = a_int, b = b_int;
	vector<vector<pii>> g(n);
	REP(i, m){
		g[u[i]].emplace_back(v[i], i);
		g[v[i]].emplace_back(u[i], i);
	}
	
	if(m == n-1){
		vector<int> pyt(m, 0);
		ll samea = ask(pyt);
		
		int kr = 0;
		for(int lewo = 0, prawo = m-1; 1;){
			if(lewo == prawo){kr = lewo; break;}
			int sr = (lewo+prawo)>>1;
			pyt = vector<int>(m, 0);
			FOR(i, lewo, sr) pyt[i] = 1;
			if(ask(pyt) > samea) prawo = sr;
			else lewo = sr+1;
		}
		int x = u[kr], y = v[kr];
		
		pyt = vector<int>(m, 0);
		function<void(int, int)> dfs_oznacz = [&](int w, int o){
			for(pii i : g[w]) if(i.fi != o) pyt[i.se] = 1, dfs_oznacz(i.fi, w);
		};
		dfs_oznacz(x, y);
		int dlx = (ask(pyt)-samea)/(b-a);
		int dly = samea/a - dlx-1;
		
		vector<pii> vec;
		function<void(int, int, int, int)> dfs_gl = [&](int w, int o, int gl, int id){
			if(!gl) return void(vec.emplace_back(id, w));
			for(pii i : g[w]) if(i.fi != o) dfs_gl(i.fi, w, gl-1, i.se);
		};
		
		dfs_gl(x, y, dlx, kr);
		int s = 0;
		for(int lewo = 0, prawo = vec.size()-1; 1;){
			if(lewo == prawo){s = vec[lewo].se; break;}
			int sr = (lewo+prawo)>>1;
			pyt = vector<int>(m, 0);
			FOR(i, lewo, sr) pyt[vec[i].fi] = 1;
			if(ask(pyt) > samea) prawo = sr;
			else lewo = sr+1;
		}
		
		vec.clear();
		dfs_gl(y, x, dly, kr);
		int t = 0;
		for(int lewo = 0, prawo = vec.size()-1; 1;){
			if(lewo == prawo){t = vec[lewo].se; break;}
			int sr = (lewo+prawo)>>1;
			pyt = vector<int>(m, 0);
			FOR(i, lewo, sr) pyt[vec[i].fi] = 1;
			if(ask(pyt) > samea) prawo = sr;
			else lewo = sr+1;
		}
		
		answer(s, t);
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 8 ms 1644 KB Output is correct
3 Correct 96 ms 8288 KB Output is correct
4 Correct 74 ms 8376 KB Output is correct
5 Correct 68 ms 8524 KB Output is correct
6 Correct 85 ms 8088 KB Output is correct
7 Correct 72 ms 8616 KB Output is correct
8 Correct 60 ms 8384 KB Output is correct
9 Correct 94 ms 8160 KB Output is correct
10 Correct 69 ms 8308 KB Output is correct
11 Correct 103 ms 8836 KB Output is correct
12 Correct 92 ms 9748 KB Output is correct
13 Correct 64 ms 8048 KB Output is correct
14 Correct 80 ms 9664 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1328 KB Output is correct
2 Correct 24 ms 2272 KB Output is correct
3 Correct 34 ms 4844 KB Output is correct
4 Correct 65 ms 10164 KB Output is correct
5 Correct 54 ms 10288 KB Output is correct
6 Correct 71 ms 11948 KB Output is correct
7 Correct 61 ms 14164 KB Output is correct
8 Correct 108 ms 9808 KB Output is correct
9 Correct 61 ms 12720 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 8 ms 1296 KB Output is correct
3 Correct 48 ms 6640 KB Output is correct
4 Correct 84 ms 8148 KB Output is correct
5 Correct 92 ms 8024 KB Output is correct
6 Correct 70 ms 8028 KB Output is correct
7 Correct 70 ms 8376 KB Output is correct
8 Correct 58 ms 8364 KB Output is correct
9 Correct 90 ms 8376 KB Output is correct
10 Correct 82 ms 8704 KB Output is correct
11 Correct 78 ms 8908 KB Output is correct
12 Correct 70 ms 8824 KB Output is correct
13 Correct 93 ms 9812 KB Output is correct
14 Correct 76 ms 9352 KB Output is correct
15 Correct 60 ms 8392 KB Output is correct
16 Correct 63 ms 8028 KB Output is correct
17 Correct 103 ms 9036 KB Output is correct
18 Correct 104 ms 9508 KB Output is correct
19 Correct 115 ms 8044 KB Output is correct
20 Correct 60 ms 8008 KB Output is correct
21 Correct 86 ms 9652 KB Output is correct
22 Correct 101 ms 9432 KB Output is correct
23 Correct 90 ms 8760 KB Output is correct
24 Correct 82 ms 9312 KB Output is correct
25 Correct 84 ms 14124 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 1112 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 7 ms 1112 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -