oj.uz

Submission #286118

# Submission time Handle Problem Language Result Execution time Memory
286118 2020-08-30T06:59:45 Z mohammad Highway Tolls (IOI18_highway) C++14
12 / 100
 343 ms 20724 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
 
#define endl "\n"
// #define int long long

typedef long long ll ;
const ll ooo = 1e14 ;
const ll oo = 2e9 ;
const double PI = acos(-1) ;
const ll M = 1e9 + 7  ;
const int N = 10000010  ;

vector<ll> g[100010] , cost;
ll a , b , p[100010];
map<pair<int,int> , int>mp;

void dis(int i){
	cost[i] = 0 ;
	priority_queue<pair<ll,ll>> q;
	q.push({0 , i});
	while(q.size()){
		ll src = q.top().second  , c = -q.top().first;
		q.pop();
		if(cost[src] < c) continue ;
		// cout << src << endl;
		for(auto x : g[src]){
			// cout << x << ' ' << cost[x] << endl;
			if(cost[x] > c + a){
				p[x] = src;
				cost[x] = c + a;
				q.push({-cost[x] , x});
			}
		}
		// cout << endl;
	}
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int M = U.size();
	a = A;b = B;
	for(int i = 0 ; i < M ; ++i) {
		g[V[i]].push_back(U[i]);
		g[U[i]].push_back(V[i]) , mp[{U[i] , V[i]}] = i , mp[{V[i] , U[i]}] = i;
	}
	cost = vector<ll>(N , ooo);
	dis(0);
	vector<int> w(M , 0);
	ll toll = ask(w);
	vector<int> ans;
	for(int i = 1 ; i < N; ++i) if(cost[i] == toll) ans.push_back(mp[{i , p[i]}]);
	while(ans.size() - 1){
		int sz = ans.size();
		for(int i = 0 ; i < sz / 2 ; ++i) w[ans[i]] = 1;
		ll tll = ask(w);
		for(int i = 0 ; i < sz / 2 ; ++i) w[ans[i]] = 0;
		if(toll == tll){
			vector<int> ans1 ;
			for(int i = sz / 2 ; i < sz ; ++i) 
				ans1.push_back(ans[i]) ;
			ans = ans1;
		}else{
			vector<int> ans1 ;
			for(int i = 0 ; i < sz / 2 ; ++i) 
				ans1.push_back(ans[i]) ;
			ans = ans1;
		}
	}
	int i = ans[0];
	ll y = (p[U[i]] == V[i] ? U[i] : V[i]);
	answer(0, y );
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2920 KB Output is correct
2 Correct 21 ms 4608 KB Output is correct
3 Correct 315 ms 20680 KB Output is correct
4 Correct 314 ms 20680 KB Output is correct
5 Correct 319 ms 20664 KB Output is correct
6 Correct 318 ms 20724 KB Output is correct
7 Correct 310 ms 20672 KB Output is correct
8 Correct 327 ms 20660 KB Output is correct
9 Correct 305 ms 20680 KB Output is correct
10 Correct 324 ms 20692 KB Output is correct
11 Correct 291 ms 19960 KB Output is correct
12 Correct 296 ms 19960 KB Output is correct
13 Correct 343 ms 20088 KB Output is correct
14 Correct 324 ms 20000 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4600 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 3 ms 2816 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 28 ms 4864 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 29 ms 4856 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -