oj.uz

Submission #933839

# Submission time Handle Problem Language Result Execution time Memory
933839 2024-02-26T11:41:09 Z kim Highway Tolls (IOI18_highway) C++17
5 / 100
 221 ms 11012 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
using pii=pair<int,int>;
#define f first
#define s second

int N,M;
vector<int> adj1[90005];
bool vis[90005];
int pre[90005],node[90005];
pii edge[130005];

vector<int> ans,tmp;
int dist;

int id0;
void bfs(int u){
  queue<int> q;
  q.push(u);
  vis[u]=1;
  while(q.size()){
    int u=q.front(); q.pop();
    pre[u]=++id0;
    node[id0]=u;
    for(auto &v:adj1[u]){
      if(!vis[v]){
        q.push(v);
        vis[v]=1;
      }
    }
  }
}

int play(int u0){
	for(int i=0;i<N;++i) vis[i]=0;
	id0=0;
	bfs(u0);

	// int l=1,r=id0;
	// while(l<r){
	// 	int mid=l+r>>1;
	// 	for(int i=0;i<M;++i){
	// 		auto &[u,v]=edge[i];
	// 		if(pre[u]<=mid&&pre[v]<=mid) tmp[i]=0;
	// 		else tmp[i]=1;
	// 	}
	// 	if(ask(tmp)==dist) r=mid;
	// 	else l=mid+1;
	// }

	  int l=1,r=id0;
	while(l<r){
		int mid=l+((r-l)>>1);
	
		for(int i=0;i<M;++i){
		auto &[u,v]=edge[i];
		if(pre[u]<=mid&&pre[v]<=mid) tmp[i]=0;
		else tmp[i]=1;
		}
	
		if(ask(tmp)==dist) r=mid;
		else l=mid+1;
	}

	ans.eb(node[l]);
	return node[l];
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	::N=N,M=U.size();
	for(int i=0;i<U.size();++i){
		adj1[U[i]].eb(V[i]);
		adj1[V[i]].eb(U[i]);
		edge[i]={U[i],V[i]};
		tmp.eb(0);
	}
	dist=ask(tmp);
	play(play(0));
	answer(ans[0],ans[1]);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i=0;i<U.size();++i){
      |              ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4248 KB Output is correct
2 Correct 8 ms 4784 KB Output is correct
3 Correct 125 ms 9568 KB Output is correct
4 Correct 116 ms 9316 KB Output is correct
5 Correct 129 ms 9788 KB Output is correct
6 Correct 112 ms 9772 KB Output is correct
7 Correct 111 ms 9780 KB Output is correct
8 Correct 110 ms 10028 KB Output is correct
9 Correct 99 ms 9564 KB Output is correct
10 Correct 118 ms 9544 KB Output is correct
11 Correct 102 ms 9420 KB Output is correct
12 Correct 124 ms 9176 KB Output is correct
13 Correct 131 ms 9636 KB Output is correct
14 Incorrect 78 ms 9164 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4768 KB Output is correct
2 Correct 20 ms 5484 KB Output is correct
3 Correct 28 ms 5904 KB Output is correct
4 Correct 99 ms 8944 KB Output is correct
5 Correct 78 ms 8928 KB Output is correct
6 Correct 67 ms 9440 KB Output is correct
7 Correct 64 ms 8936 KB Output is correct
8 Correct 72 ms 8932 KB Output is correct
9 Incorrect 54 ms 9204 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4184 KB Output is correct
2 Correct 11 ms 4968 KB Output is correct
3 Correct 72 ms 8280 KB Output is correct
4 Correct 92 ms 9276 KB Output is correct
5 Correct 79 ms 9088 KB Output is correct
6 Correct 81 ms 9312 KB Output is correct
7 Correct 90 ms 9320 KB Output is correct
8 Correct 92 ms 9992 KB Output is correct
9 Incorrect 80 ms 9328 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4992 KB Output is correct
2 Correct 14 ms 4848 KB Output is correct
3 Correct 113 ms 9784 KB Output is correct
4 Correct 107 ms 9812 KB Output is correct
5 Correct 221 ms 10792 KB Output is correct
6 Correct 136 ms 11012 KB Output is correct
7 Correct 155 ms 10776 KB Output is correct
8 Incorrect 150 ms 10752 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 4820 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -