oj.uz

Submission #1012640

# Submission time Handle Problem Language Result Execution time Memory
1012640 2024-07-02T12:47:39 Z Belphegor Highway Tolls (IOI18_highway) C++14
51 / 100
 109 ms 12860 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){
	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;
    ll 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>c1,c2;
	for(int i=0; i<n; i++){
		if(dist_a[i] < dist_b[i]) c1.emplace_back(i);
		if(dist_a[i] > dist_b[i]) c2.emplace_back(i);
	}
	answer(FIND(w,c1,a,e),FIND(w,c2,b,e));
}

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 8 ms 4696 KB Output is correct
3 Correct 89 ms 11968 KB Output is correct
4 Correct 91 ms 11676 KB Output is correct
5 Correct 86 ms 11696 KB Output is correct
6 Correct 82 ms 11704 KB Output is correct
7 Correct 102 ms 11476 KB Output is correct
8 Correct 92 ms 11676 KB Output is correct
9 Correct 97 ms 12064 KB Output is correct
10 Correct 82 ms 11596 KB Output is correct
11 Correct 84 ms 10992 KB Output is correct
12 Correct 96 ms 11588 KB Output is correct
13 Correct 81 ms 10904 KB Output is correct
14 Correct 94 ms 11820 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4696 KB Output is correct
2 Correct 17 ms 5440 KB Output is correct
3 Correct 24 ms 6252 KB Output is correct
4 Correct 72 ms 11136 KB Output is correct
5 Correct 67 ms 10876 KB Output is correct
6 Correct 70 ms 10864 KB Output is correct
7 Correct 72 ms 11432 KB Output is correct
8 Correct 70 ms 10524 KB Output is correct
9 Correct 76 ms 11584 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3672 KB Output is correct
2 Correct 9 ms 4700 KB Output is correct
3 Correct 63 ms 9936 KB Output is correct
4 Correct 82 ms 11632 KB Output is correct
5 Correct 82 ms 11996 KB Output is correct
6 Correct 74 ms 11664 KB Output is correct
7 Correct 73 ms 12116 KB Output is correct
8 Correct 73 ms 12356 KB Output is correct
9 Correct 94 ms 12420 KB Output is correct
10 Correct 89 ms 11960 KB Output is correct
11 Correct 92 ms 11588 KB Output is correct
12 Correct 90 ms 10892 KB Output is correct
13 Correct 89 ms 11612 KB Output is correct
14 Correct 91 ms 11136 KB Output is correct
15 Correct 79 ms 11676 KB Output is correct
16 Correct 89 ms 11624 KB Output is correct
17 Correct 90 ms 12184 KB Output is correct
18 Correct 87 ms 11600 KB Output is correct
19 Correct 88 ms 12092 KB Output is correct
20 Correct 87 ms 10892 KB Output is correct
21 Correct 87 ms 12508 KB Output is correct
22 Correct 81 ms 12860 KB Output is correct
23 Correct 99 ms 11704 KB Output is correct
24 Correct 94 ms 11680 KB Output is correct
25 Correct 109 ms 11664 KB Output is correct

Subtask #5
0 / 18.0

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