oj.uz

Submission #138827

# Submission time Handle Problem Language Result Execution time Memory
138827 2019-07-30T12:27:26 Z muradeyn Highway Tolls (IOI18_highway) C++14
5 / 100
 364 ms 19344 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define F first
#define S second

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;
		int 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:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0;i<cur.size() / 2;i++) {
                  ~^~~~~~~~~~~~~~~
highway.cpp:52: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 2568 KB Output is correct
2 Correct 4 ms 2552 KB Output is correct
3 Correct 4 ms 2552 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2624 KB Output is correct
7 Correct 5 ms 2680 KB Output is correct
8 Correct 4 ms 2552 KB Output is correct
9 Correct 5 ms 2612 KB Output is correct
10 Correct 4 ms 2552 KB Output is correct
11 Correct 4 ms 2680 KB Output is correct
12 Correct 4 ms 2680 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 31 ms 4344 KB Output is correct
3 Correct 352 ms 19076 KB Output is correct
4 Correct 364 ms 18932 KB Output is correct
5 Correct 338 ms 18868 KB Output is correct
6 Correct 339 ms 18692 KB Output is correct
7 Correct 339 ms 18828 KB Output is correct
8 Correct 341 ms 18888 KB Output is correct
9 Correct 339 ms 18672 KB Output is correct
10 Correct 345 ms 18884 KB Output is correct
11 Correct 323 ms 18728 KB Output is correct
12 Correct 338 ms 19344 KB Output is correct
13 Correct 318 ms 19176 KB Output is correct
14 Incorrect 336 ms 18608 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 4324 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 6 ms 2808 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 66 ms 6096 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 37 ms 4788 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -