oj.uz

Submission #625115

# Submission time Handle Problem Language Result Execution time Memory
625115 2022-08-09T11:45:02 Z MateGiorbelidze Highway Tolls (IOI18_highway) C++14
51 / 100
 389 ms 20752 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

vector<int> g[90001] , ans;

vector<bool> used(90001);

map <pair<int,int>, int> mp;

vector<int> vask;

vector<int> v, u , a(130001), d(130001);

int n , m , sm , bg;
ll mn;

void bfs (int rt) {
    queue <int> q;
    q.push(rt);
    
    for (int i = 0; i < n; i++)
    	used[i] = 0;
    
    int timer = 0;
    while(!q.empty()){
    	
        int v = q.front();
        q.pop();
        used[v] = 1;
        
        for(int k : g[v]){
            if(used[k] != 0) continue;
            a[timer++] = mp[{v , k}];
            d[mp[{v , k}]] = k;
            
            q.push(k);
        }
        
    }
	
}

void find_ans(int rt) {
	
	int l = 0 , r = n - 2;
	
	bfs(rt);
	
	//cout<<d[4];
	while (l < r) {
		
		int mid = (l + r) / 2;
		
		for (int i = 0; i <= mid; i++) {
			
			vask[a[i]] = 0;
			
		}
		
		for (int i = mid + 1; i <= r; i++) {
			
			vask[a[i]] = 1;
			//cout<<a[i]<" ";
			
		}
		
		ll curs = ask(vask);
		
		if (curs > mn) l = mid + 1;
		else r = mid;
	}
	
	ans.pb(d[a[l]]);
	
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  	n = N; u = U; v = V, sm = A; bg = B;
  	
  	m = u.size();
  	
  	
  	for (int i = 0; i < m; i++) {
  		vask.pb(0);
  		
  		g[u[i]].pb(v[i]);
  		g[v[i]].pb(u[i]);
  		
  		mp[{u[i] , v[i]}] = mp[{v[i] , u[i]}] = i;
	}
	
	mn = ask(vask);
	
	find_ans(0);
	//cout<<ans[0];
	find_ans(ans[0]);
	//cout<<ans[1];
	//cout<<d[a[l]];
	
	answer(ans[0] , ans[1]);
	
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3536 KB Output is correct
2 Correct 20 ms 5360 KB Output is correct
3 Correct 312 ms 20172 KB Output is correct
4 Correct 338 ms 20312 KB Output is correct
5 Correct 344 ms 20156 KB Output is correct
6 Correct 309 ms 20256 KB Output is correct
7 Correct 314 ms 20204 KB Output is correct
8 Correct 298 ms 20216 KB Output is correct
9 Correct 298 ms 20164 KB Output is correct
10 Correct 301 ms 20144 KB Output is correct
11 Correct 343 ms 20008 KB Output is correct
12 Correct 389 ms 20316 KB Output is correct
13 Correct 332 ms 20000 KB Output is correct
14 Correct 328 ms 20124 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5200 KB Output is correct
2 Correct 33 ms 7068 KB Output is correct
3 Correct 48 ms 9044 KB Output is correct
4 Correct 188 ms 20008 KB Output is correct
5 Correct 195 ms 20012 KB Output is correct
6 Correct 178 ms 20004 KB Output is correct
7 Correct 193 ms 20040 KB Output is correct
8 Correct 164 ms 19996 KB Output is correct
9 Correct 150 ms 20008 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3536 KB Output is correct
2 Correct 21 ms 5316 KB Output is correct
3 Correct 243 ms 16520 KB Output is correct
4 Correct 298 ms 20156 KB Output is correct
5 Correct 321 ms 20232 KB Output is correct
6 Correct 314 ms 20200 KB Output is correct
7 Correct 301 ms 20196 KB Output is correct
8 Correct 346 ms 20140 KB Output is correct
9 Correct 309 ms 20160 KB Output is correct
10 Correct 342 ms 20188 KB Output is correct
11 Correct 327 ms 19996 KB Output is correct
12 Correct 333 ms 20132 KB Output is correct
13 Correct 372 ms 20088 KB Output is correct
14 Correct 320 ms 20072 KB Output is correct
15 Correct 291 ms 20212 KB Output is correct
16 Correct 306 ms 20256 KB Output is correct
17 Correct 326 ms 19996 KB Output is correct
18 Correct 323 ms 20032 KB Output is correct
19 Correct 337 ms 20336 KB Output is correct
20 Correct 313 ms 20020 KB Output is correct
21 Correct 301 ms 20732 KB Output is correct
22 Correct 301 ms 20752 KB Output is correct
23 Correct 364 ms 20660 KB Output is correct
24 Correct 337 ms 20488 KB Output is correct
25 Correct 310 ms 20184 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 5476 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 33 ms 5476 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -