oj.uz

Submission #139929

# Submission time Handle Problem Language Result Execution time Memory
139929 2019-08-01T16:45:47 Z almogwald Highway Tolls (IOI18_highway) C++14
51 / 100
 618 ms 262148 KB 
#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <iostream>
#include "highway.h"
//#include "doll.h"
#define fori(i,n) for(int i=0;i<n;i++)
#define forn(i,n) for(int i=1;i<n;i++)
#define fort(i,m,n) for(int i=m;i<n;i++)
#define forib(i,n) for(int i=n-1;i>=0;i--)
#define fornb(i,n) for(int i=n-1;i>0;i--)
#define maxl 10000000000
#define con continue;
typedef long long lol;
using namespace std;
typedef vector<int> veci;
typedef pair<lol,lol> point;
lol sum=0;

void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
	int m = U.size();
	veci w(m);
	lol toll = ask(w);
	vector<vector<point>> cons(n);
	fori(i,m){
		cons[U[i]].push_back({V[i],i});
		cons[V[i]].push_back({U[i],i});
	}
	veci ord;
	vector<point>x;
	x.push_back({0,-1});
	veci p(n);
	while(!x.empty()){
		int cur=x.back().first;
		int pp=x.back().second;
		x.pop_back();
		p[cur]=pp;
		ord.push_back(pp);
		fori(i,cons[cur].size()){
			if(cons[cur][i].second!=pp){
				x.push_back(cons[cur][i]);
			}
		}
	}
	int l=1,h=m;
	while(l<h){
		int mid=(l+h+1)/2;
		fori(i,m){
			w[i]=0;
		}
		fort(i,mid,h+1){
			w[ord[i]]=1;
		}
		lol tol = ask(w);
		if(tol==toll){
			h=mid-1;
		}else{
			l=mid;
		}
	}
	l=ord[l];
	int s=0;
	fori(i,n){
		if(p[i]==l){
			s=i;
			break;
		}
	}
	ord.resize(0);

	x.push_back({s,-1});

	while(!x.empty()){
		int cur=x.back().first;
		int pp=x.back().second;
		x.pop_back();
		p[cur]=pp;
		ord.push_back(pp);
		fori(i,cons[cur].size()){
			if(cons[cur][i].second!=pp){
				x.push_back(cons[cur][i]);
			}
		}
	}
	l=1,h=m;
	while(l<h){
		int mid=(l+h+1)/2;
		fori(i,m){
			w[i]=0;
		}
		fort(i,mid,h+1){
			w[ord[i]]=1;
		}
		lol tol = ask(w);
		if(tol==toll){
			h=mid-1;
		}else{
			l=mid;
		}
	}
	l=ord[l];
	int t=0;
	fori(i,n){
		if(p[i]==l){
			t=i;
			break;
		}
	}
	answer(s, t);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:9:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
highway.cpp:41:8:
   fori(i,cons[cur].size()){
        ~~~~~~~~~~~~~~~~~~       
highway.cpp:41:3: note: in expansion of macro 'fori'
   fori(i,cons[cur].size()){
   ^~~~
highway.cpp:9:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
highway.cpp:81:8:
   fori(i,cons[cur].size()){
        ~~~~~~~~~~~~~~~~~~       
highway.cpp:81:3: note: in expansion of macro 'fori'
   fori(i,cons[cur].size()){
   ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 316 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 2 ms 316 KB Output is correct
5 Correct 2 ms 312 KB Output is correct
6 Correct 2 ms 320 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 2 ms 316 KB Output is correct
9 Correct 2 ms 320 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 2 ms 276 KB Output is correct
12 Correct 2 ms 248 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 35 ms 1420 KB Output is correct
3 Correct 166 ms 9860 KB Output is correct
4 Correct 157 ms 9772 KB Output is correct
5 Correct 202 ms 9764 KB Output is correct
6 Correct 221 ms 9740 KB Output is correct
7 Correct 179 ms 9800 KB Output is correct
8 Correct 245 ms 9768 KB Output is correct
9 Correct 199 ms 9796 KB Output is correct
10 Correct 197 ms 9768 KB Output is correct
11 Correct 219 ms 9864 KB Output is correct
12 Correct 182 ms 9892 KB Output is correct
13 Correct 227 ms 9824 KB Output is correct
14 Correct 222 ms 9896 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1272 KB Output is correct
2 Correct 28 ms 2424 KB Output is correct
3 Correct 48 ms 3408 KB Output is correct
4 Correct 143 ms 9340 KB Output is correct
5 Correct 138 ms 9516 KB Output is correct
6 Correct 149 ms 9312 KB Output is correct
7 Correct 144 ms 9336 KB Output is correct
8 Correct 149 ms 9384 KB Output is correct
9 Correct 155 ms 9348 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 424 KB Output is correct
2 Correct 12 ms 1428 KB Output is correct
3 Correct 154 ms 7844 KB Output is correct
4 Correct 191 ms 9840 KB Output is correct
5 Correct 177 ms 9892 KB Output is correct
6 Correct 226 ms 9808 KB Output is correct
7 Correct 201 ms 9720 KB Output is correct
8 Correct 160 ms 9776 KB Output is correct
9 Correct 206 ms 9724 KB Output is correct
10 Correct 172 ms 9768 KB Output is correct
11 Correct 213 ms 9980 KB Output is correct
12 Correct 219 ms 9768 KB Output is correct
13 Correct 243 ms 9788 KB Output is correct
14 Correct 203 ms 9776 KB Output is correct
15 Correct 200 ms 9724 KB Output is correct
16 Correct 186 ms 9720 KB Output is correct
17 Correct 226 ms 9852 KB Output is correct
18 Correct 199 ms 9764 KB Output is correct
19 Correct 196 ms 9736 KB Output is correct
20 Correct 215 ms 9892 KB Output is correct
21 Correct 173 ms 11776 KB Output is correct
22 Correct 178 ms 11816 KB Output is correct
23 Correct 166 ms 11000 KB Output is correct
24 Correct 191 ms 11652 KB Output is correct
25 Correct 206 ms 9984 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 618 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 582 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -