oj.uz

Submission #1012631

# Submission time Handle Problem Language Result Execution time Memory
1012631 2024-07-02T12:31:43 Z Belphegor Highway Tolls (IOI18_highway) C++14
51 / 100
 97 ms 12520 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int sz = 100000;
vector<pi>tree[sz+5];
int visited[sz+5];
int dist_a[sz+5],dist_b[sz+5];
int FIND(vector<int>w,vector<int>candidates,int root,int edge,ll d){
	memset(visited,0,sizeof(visited));
	
	for(int x : candidates) visited[x] = 1;
    w=vector<int>(w.size(),1);
    
    visited[root] = 0;
	queue<int>q; q.push(root);
	vector<pi>v; v.emplace_back(pi(root,edge));
	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(pi p : tree[cur]){
			int nxt = p.first;
			int id = p.second;
			if(visited[nxt]){
				visited[nxt] = 0;
				v.emplace_back(pi(nxt,id));
				q.push(nxt);
			}
		}
	}
	reverse(v.begin(),v.end());
    for(pi p : v) w[p.second]=0;
    d=ask(w);
	int l = 0,r = v.size()-1;
	while(l<=r){
		int M = (l+r)>>1;
		for(int i=0; i<=M; i++) w[v[i].second] = 1;
		if(ask(w) > d) r = M-1;
		else l = M+1;
		for(int i=0; i<=M; i++) w[v[i].second] = 0;
	}
	return v[l].first;
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
	for(int i=0; i<n; i++){
		tree[i].clear();
		visited[i] = 0;
		dist_a[i] = dist_b[i] = 1e9;
	}
	int m = U.size();
	for(int i=0; i<U.size(); i++){
		int a = U[i],b = V[i];
		tree[a].emplace_back(pi(b,i));
		tree[b].emplace_back(pi(a,i));
	}
	vector<int>w(m,0);
	ll d = ask(w);
	int l = 0,r = m-1;
	while(l<=r){
		int M = (l+r)>>1;
		for(int i=0; i<=M; i++) w[i] = 1;
		if(ask(w) > d) r = M-1;
		else l = M+1;
		for(int i=0; i<=M; i++) w[i] = 0;
	}
	int e = l;
	int a = U[e],b = V[e];
	dist_a[a] = 0; 
	queue<int>q; q.push(a);
	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(pi p : tree[cur]){
			int nxt = p.first;
			int id = p.second;
			if(dist_a[nxt] > dist_a[cur] + 1){
				dist_a[nxt] = dist_a[cur] + 1;
				q.push(nxt);
			}
		}
	}
	dist_b[b] = 0; 
	q.push(b);
	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(pi p : tree[cur]){
			int nxt = p.first;
			int id = p.second;
			if(dist_b[nxt] > dist_b[cur] + 1){
				dist_b[nxt] = dist_b[cur] + 1;
				q.push(nxt);
			}
		}
	}
	vector<int>c;
	for(int i=0; i<n; i++){
		if(dist_a[i] < dist_b[i]) c.emplace_back(i);
	}
	a = FIND(w,c,a,e,d); c.clear();
	for(int i=0; i<n; i++){
		if(dist_b[i] < dist_a[i]) c.emplace_back(i);
	}
	b = FIND(w,c,b,e,d); c.clear();
	answer(a,b);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0; i<U.size(); i++){
      |               ~^~~~~~~~~
highway.cpp:74:8: warning: unused variable 'id' [-Wunused-variable]
   74 |    int id = p.second;
      |        ^~
highway.cpp:87:8: warning: unused variable 'id' [-Wunused-variable]
   87 |    int id = p.second;
      |        ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3060 KB Output is correct
2 Correct 9 ms 4184 KB Output is correct
3 Correct 84 ms 11584 KB Output is correct
4 Correct 85 ms 11612 KB Output is correct
5 Correct 84 ms 11560 KB Output is correct
6 Correct 92 ms 11556 KB Output is correct
7 Correct 90 ms 11500 KB Output is correct
8 Correct 87 ms 11680 KB Output is correct
9 Correct 74 ms 11440 KB Output is correct
10 Correct 77 ms 11568 KB Output is correct
11 Correct 83 ms 10984 KB Output is correct
12 Correct 84 ms 10844 KB Output is correct
13 Correct 83 ms 11008 KB Output is correct
14 Correct 97 ms 11120 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3928 KB Output is correct
2 Correct 16 ms 4856 KB Output is correct
3 Correct 21 ms 5656 KB Output is correct
4 Correct 69 ms 10320 KB Output is correct
5 Correct 67 ms 10656 KB Output is correct
6 Correct 64 ms 10992 KB Output is correct
7 Correct 70 ms 11040 KB Output is correct
8 Correct 71 ms 10820 KB Output is correct
9 Correct 65 ms 10696 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 9 ms 3892 KB Output is correct
3 Correct 55 ms 10052 KB Output is correct
4 Correct 84 ms 12088 KB Output is correct
5 Correct 84 ms 11412 KB Output is correct
6 Correct 86 ms 11576 KB Output is correct
7 Correct 75 ms 11464 KB Output is correct
8 Correct 76 ms 11620 KB Output is correct
9 Correct 82 ms 11556 KB Output is correct
10 Correct 86 ms 11464 KB Output is correct
11 Correct 87 ms 10928 KB Output is correct
12 Correct 91 ms 11048 KB Output is correct
13 Correct 94 ms 10916 KB Output is correct
14 Correct 93 ms 10264 KB Output is correct
15 Correct 78 ms 11676 KB Output is correct
16 Correct 86 ms 11568 KB Output is correct
17 Correct 77 ms 10980 KB Output is correct
18 Correct 88 ms 11104 KB Output is correct
19 Correct 70 ms 11600 KB Output is correct
20 Correct 79 ms 10928 KB Output is correct
21 Correct 71 ms 12520 KB Output is correct
22 Correct 76 ms 12432 KB Output is correct
23 Correct 71 ms 10908 KB Output is correct
24 Correct 79 ms 10804 KB Output is correct
25 Correct 81 ms 11100 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 4036 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 12 ms 4120 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -