oj.uz

Submission #138832

# Submission time Handle Problem Language Result Execution time Memory
138832 2019-07-30T12:31:43 Z muradeyn Highway Tolls (IOI18_highway) C++14
12 / 100
 394 ms 19304 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);
	intt 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 = 1LL * 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 2680 KB Output is correct
2 Correct 4 ms 2552 KB Output is correct
3 Correct 4 ms 2552 KB Output is correct
4 Correct 4 ms 2600 KB Output is correct
5 Correct 4 ms 2600 KB Output is correct
6 Correct 4 ms 2556 KB Output is correct
7 Correct 4 ms 2600 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 4 ms 2684 KB Output is correct
10 Correct 4 ms 2552 KB Output is correct
11 Correct 4 ms 2552 KB Output is correct
12 Correct 4 ms 2552 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2924 KB Output is correct
2 Correct 29 ms 4344 KB Output is correct
3 Correct 348 ms 18844 KB Output is correct
4 Correct 394 ms 18884 KB Output is correct
5 Correct 377 ms 18860 KB Output is correct
6 Correct 321 ms 18708 KB Output is correct
7 Correct 349 ms 18780 KB Output is correct
8 Correct 330 ms 18888 KB Output is correct
9 Correct 335 ms 18668 KB Output is correct
10 Correct 358 ms 18888 KB Output is correct
11 Correct 335 ms 18732 KB Output is correct
12 Correct 335 ms 19200 KB Output is correct
13 Correct 343 ms 19048 KB Output is correct
14 Correct 330 ms 19304 KB Output is correct

Subtask #3
0 / 6.0

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