oj.uz

Submission #138830

# Submission time Handle Problem Language Result Execution time Memory
138830 2019-07-30T12:29:42 Z muradeyn Highway Tolls (IOI18_highway) C++14
5 / 100
 371 ms 19192 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define intt long long 

using namespace std;

const int maxx = 100000;

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

vector<int>v[maxx];

vector<int>w;

vector< pair<int,int> >cur;

int x , y;

void dfs(int s,int p,int d,int need) {
	if (d == need) {
		cur.push_back({p , s});
		return;
	}
	for (int to : v[s]) {
		if (to == p)continue;
		dfs(to , s , d + 1 , need);
	}
}

void find_pair(int n, vector<int> u, vector<int> vv, int a, int b) {
	int m = u.size();
	for (int i = 0;i<m;i++) {
		x = u[i];
		y = vv[i];
		mp[{x , y}] = mp[{y , x}] = i;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	w.resize(m , 0);
	int ret = ask(w);
	int dist = ret / a;
	dfs(0 , 0 , 0 , dist);
	while (cur.size() > 1) {
		vector< pair<int,int> >lft;
		vector< pair<int,int> >rgt;
		intt lw = dist * a;
		for (int i = 0;i<cur.size() / 2;i++) {
			w[mp[{cur[i].F , cur[i].S}]] = 0;
			lft.push_back(cur[i]);
		}
		for (int i = cur.size() / 2;i<cur.size();i++) {
			w[mp[{cur[i].F , cur[i].S}]] = 1;
			rgt.push_back(cur[i]);
		}
		ret = ask(w);
		if (ret == lw)cur = lft;
		else cur = rgt;
	}
	answer(0 , cur.back().S);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0;i<cur.size() / 2;i++) {
                  ~^~~~~~~~~~~~~~~
highway.cpp:53:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = cur.size() / 2;i<cur.size();i++) {
                               ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2924 KB Output is correct
2 Correct 37 ms 4516 KB Output is correct
3 Correct 368 ms 18844 KB Output is correct
4 Correct 371 ms 18884 KB Output is correct
5 Correct 365 ms 18880 KB Output is correct
6 Correct 347 ms 18640 KB Output is correct
7 Correct 336 ms 18788 KB Output is correct
8 Correct 360 ms 18872 KB Output is correct
9 Correct 353 ms 18744 KB Output is correct
10 Correct 357 ms 18936 KB Output is correct
11 Correct 316 ms 18732 KB Output is correct
12 Correct 347 ms 19192 KB Output is correct
13 Correct 319 ms 18988 KB Output is correct
14 Incorrect 343 ms 18480 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 4340 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 5 ms 2728 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 67 ms 6104 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 31 ms 4564 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -