oj.uz

Submission #933836

# Submission time Handle Problem Language Result Execution time Memory
933836 2024-02-26T11:39:05 Z kim Highway Tolls (IOI18_highway) C++17
5 / 100
 185 ms 11084 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;
	}
	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 'int play(int)':
highway.cpp:42:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int mid=l+r>>1;
      |           ~^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  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 1 ms 4188 KB Output is correct
3 Correct 1 ms 4188 KB Output is correct
4 Correct 1 ms 4188 KB Output is correct
5 Correct 1 ms 4184 KB Output is correct
6 Correct 1 ms 4188 KB Output is correct
7 Correct 1 ms 4184 KB Output is correct
8 Correct 2 ms 4200 KB Output is correct
9 Correct 1 ms 4192 KB Output is correct
10 Correct 1 ms 4196 KB Output is correct
11 Correct 2 ms 4188 KB Output is correct
12 Correct 1 ms 4196 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 10 ms 4964 KB Output is correct
3 Correct 115 ms 10028 KB Output is correct
4 Correct 88 ms 9316 KB Output is correct
5 Correct 124 ms 9764 KB Output is correct
6 Correct 85 ms 9080 KB Output is correct
7 Correct 98 ms 9788 KB Output is correct
8 Correct 100 ms 9312 KB Output is correct
9 Correct 95 ms 9540 KB Output is correct
10 Correct 98 ms 9544 KB Output is correct
11 Correct 149 ms 9624 KB Output is correct
12 Correct 135 ms 9888 KB Output is correct
13 Correct 120 ms 9892 KB Output is correct
14 Incorrect 97 ms 9416 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 14 ms 4952 KB Output is correct
2 Correct 22 ms 5352 KB Output is correct
3 Correct 26 ms 5876 KB Output is correct
4 Correct 79 ms 8932 KB Output is correct
5 Correct 66 ms 9184 KB Output is correct
6 Correct 85 ms 9184 KB Output is correct
7 Correct 64 ms 8932 KB Output is correct
8 Correct 86 ms 9188 KB Output is correct
9 Incorrect 81 ms 9176 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 2 ms 4184 KB Output is correct
2 Correct 17 ms 4964 KB Output is correct
3 Correct 81 ms 8280 KB Output is correct
4 Correct 126 ms 9528 KB Output is correct
5 Correct 108 ms 9372 KB Output is correct
6 Correct 85 ms 9556 KB Output is correct
7 Correct 115 ms 9320 KB Output is correct
8 Correct 96 ms 9540 KB Output is correct
9 Incorrect 87 ms 9292 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 5016 KB Output is correct
3 Correct 142 ms 9800 KB Output is correct
4 Correct 126 ms 10032 KB Output is correct
5 Correct 185 ms 11084 KB Output is correct
6 Correct 132 ms 10776 KB Output is correct
7 Correct 158 ms 10764 KB Output is correct
8 Incorrect 145 ms 10796 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 11 ms 5000 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -