oj.uz

Submission #294582

# Submission time Handle Problem Language Result Execution time Memory
294582 2020-09-09T06:17:35 Z Dovran Highway Tolls (IOI18_highway) C++11
100 / 100
 1029 ms 39344 KB 
#include <bits/stdc++.h>
#include "highway.h"
#define N 200009
#define pii pair <int, int>
#define ff first
#define ss second
#define sz size
#define pb push_back
#define ll long long

using namespace std;

ll m, ln;
vector<ll>e[N];
vector<int>asd;
map<ll, ll>c[N];

int tap(vector<int>v){
	int l=0, r=v.sz()-1, in;
	while(l<=r){
		int md=(l+r)/2;
		for(int i=0; i<m; i++)
			asd[i]=0;
		for(int i=md; i<v.size(); i++)
			for(auto j:e[v[i]]) asd[c[v[i]][j]]=1;
		ll x=ask(asd);
		if(x!=ln)
			in=md, l=md+1;
		else r=md-1;
		
	}
	return v[in];
}

void find_pair(int n, std::vector<int>u, std::vector<int>v, int a, int b){
	m=u.size();
	for(int i=0; i<m; i++){
		e[u[i]].pb(v[i]);
		e[v[i]].pb(u[i]);
		
		c[v[i]][u[i]]=i;
		c[u[i]][v[i]]=i;
		
		
		asd.pb(0);
	}
	ln=ask(asd);
	int l=0, r=m-1;
	ll x, in;
	while(r>=l){
		int md=(l+r)/2;
		for(int i = 0; i < m; i++){
			if(i<=md) asd[i] = 1;
			else asd[i]=0;
		}
		
		x=ask(asd);
		
		if(x==ln) l=md+1;
		else in = md, r=md-1;
	}
//	answer(0, 0);
//	return;
	queue<pii> q;
	q.push({u[in], 1});
	q.push({v[in], 2});
	int vis[N];
	vis[u[in]]=1;
	vis[v[in]]=2;
	
	vector<int> C, D;
	while(!q.empty()){
		int nd=q.front().ff;
		int tp=q.front().ss;
		q.pop();
		vis[nd]=tp;
		if(tp==1)
			C.pb(nd);
		else
			D.pb(nd);
		
		for(auto i:e[nd])
			if(!vis[i])
				vis[i]=tp, q.push({i, tp});
	}
	answer(tap(C), tap(D));
}

Compilation message

highway.cpp: In function 'int tap(std::vector<int>)':
highway.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int i=md; i<v.size(); i++)
      |                 ~^~~~~~~~~
highway.cpp:32:13: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |  return v[in];
      |             ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:65:14: warning: 'in' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |  q.push({u[in], 1});
      |              ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14592 KB Output is correct
2 Correct 37 ms 16384 KB Output is correct
3 Correct 440 ms 32168 KB Output is correct
4 Correct 379 ms 32172 KB Output is correct
5 Correct 432 ms 32476 KB Output is correct
6 Correct 296 ms 32156 KB Output is correct
7 Correct 444 ms 32232 KB Output is correct
8 Correct 717 ms 32264 KB Output is correct
9 Correct 749 ms 32288 KB Output is correct
10 Correct 379 ms 32172 KB Output is correct
11 Correct 560 ms 31532 KB Output is correct
12 Correct 503 ms 31672 KB Output is correct
13 Correct 512 ms 31688 KB Output is correct
14 Correct 507 ms 31584 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16376 KB Output is correct
2 Correct 44 ms 18284 KB Output is correct
3 Correct 79 ms 20124 KB Output is correct
4 Correct 171 ms 31528 KB Output is correct
5 Correct 228 ms 31472 KB Output is correct
6 Correct 133 ms 31720 KB Output is correct
7 Correct 178 ms 31588 KB Output is correct
8 Correct 196 ms 31656 KB Output is correct
9 Correct 229 ms 31604 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14592 KB Output is correct
2 Correct 43 ms 16424 KB Output is correct
3 Correct 505 ms 28360 KB Output is correct
4 Correct 659 ms 32156 KB Output is correct
5 Correct 735 ms 32348 KB Output is correct
6 Correct 791 ms 32252 KB Output is correct
7 Correct 754 ms 32172 KB Output is correct
8 Correct 745 ms 32212 KB Output is correct
9 Correct 506 ms 32184 KB Output is correct
10 Correct 557 ms 32288 KB Output is correct
11 Correct 464 ms 31628 KB Output is correct
12 Correct 347 ms 31748 KB Output is correct
13 Correct 489 ms 31708 KB Output is correct
14 Correct 508 ms 31716 KB Output is correct
15 Correct 685 ms 32300 KB Output is correct
16 Correct 666 ms 32180 KB Output is correct
17 Correct 422 ms 31600 KB Output is correct
18 Correct 503 ms 31540 KB Output is correct
19 Correct 768 ms 32376 KB Output is correct
20 Correct 596 ms 31620 KB Output is correct
21 Correct 328 ms 32988 KB Output is correct
22 Correct 299 ms 32992 KB Output is correct
23 Correct 334 ms 32364 KB Output is correct
24 Correct 308 ms 32260 KB Output is correct
25 Correct 310 ms 31696 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 16512 KB Output is correct
2 Correct 45 ms 16760 KB Output is correct
3 Correct 363 ms 33868 KB Output is correct
4 Correct 559 ms 35628 KB Output is correct
5 Correct 946 ms 39048 KB Output is correct
6 Correct 884 ms 38936 KB Output is correct
7 Correct 995 ms 39156 KB Output is correct
8 Correct 678 ms 39108 KB Output is correct
9 Correct 728 ms 37380 KB Output is correct
10 Correct 753 ms 38392 KB Output is correct
11 Correct 523 ms 38496 KB Output is correct
12 Correct 800 ms 38748 KB Output is correct
13 Correct 993 ms 38976 KB Output is correct
14 Correct 841 ms 39100 KB Output is correct
15 Correct 924 ms 39064 KB Output is correct
16 Correct 572 ms 38080 KB Output is correct
17 Correct 425 ms 32996 KB Output is correct
18 Correct 518 ms 33060 KB Output is correct
19 Correct 305 ms 33124 KB Output is correct
20 Correct 518 ms 33504 KB Output is correct
21 Correct 857 ms 38924 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 16712 KB Output is correct
2 Correct 37 ms 16760 KB Output is correct
3 Correct 812 ms 34180 KB Output is correct
4 Correct 815 ms 34736 KB Output is correct
5 Correct 820 ms 35676 KB Output is correct
6 Correct 781 ms 38940 KB Output is correct
7 Correct 668 ms 34132 KB Output is correct
8 Correct 815 ms 34772 KB Output is correct
9 Correct 828 ms 35344 KB Output is correct
10 Correct 925 ms 39192 KB Output is correct
11 Correct 958 ms 39076 KB Output is correct
12 Correct 930 ms 39012 KB Output is correct
13 Correct 684 ms 38536 KB Output is correct
14 Correct 733 ms 38508 KB Output is correct
15 Correct 721 ms 38556 KB Output is correct
16 Correct 750 ms 38504 KB Output is correct
17 Correct 595 ms 38420 KB Output is correct
18 Correct 607 ms 38348 KB Output is correct
19 Correct 921 ms 38800 KB Output is correct
20 Correct 1029 ms 39064 KB Output is correct
21 Correct 967 ms 39216 KB Output is correct
22 Correct 893 ms 39032 KB Output is correct
23 Correct 940 ms 39096 KB Output is correct
24 Correct 826 ms 39344 KB Output is correct
25 Correct 930 ms 39160 KB Output is correct
26 Correct 913 ms 39152 KB Output is correct
27 Correct 371 ms 32964 KB Output is correct
28 Correct 511 ms 33120 KB Output is correct
29 Correct 577 ms 33252 KB Output is correct
30 Correct 325 ms 33088 KB Output is correct
31 Correct 446 ms 33168 KB Output is correct
32 Correct 478 ms 33252 KB Output is correct
33 Correct 354 ms 33508 KB Output is correct
34 Correct 563 ms 33068 KB Output is correct
35 Correct 506 ms 32984 KB Output is correct
36 Correct 543 ms 32996 KB Output is correct
37 Correct 519 ms 33380 KB Output is correct
38 Correct 327 ms 33752 KB Output is correct
39 Correct 846 ms 39192 KB Output is correct
40 Correct 847 ms 39136 KB Output is correct
41 Correct 420 ms 38968 KB Output is correct
42 Correct 851 ms 38984 KB Output is correct