oj.uz

Submission #933831

# Submission time Handle Problem Language Result Execution time Memory
933831 2024-02-26T11:32:36 Z kim Highway Tolls (IOI18_highway) C++17
5 / 100
 154 ms 9936 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

using ti3=tuple<int,int,int>;

vector<int> adj1[90005];
bitset<90005> vis;
int pre[90005],node[90005];

vector<int> ans,tmp;
int dist;
int play(int n,vector<int> &U,vector<int> &V,int u0){
	vis=0;
	int m=U.size();
	int id=0;
	{
		queue<int> q;
		q.emplace(u0);
		vis[u0]=1;
		while(q.size()){
			int u=q.front(); q.pop();
			pre[u]=++id;
			node[id]=u;
			for(auto &v:adj1[u]){
				if(vis[v]) continue;
				vis[v]=1;
				q.emplace(v);
			}
		}
	}
	int l=1,r=id;
	while(l<r){
		int mid=l+r>>1;
		for(int i=0;i<m;++i){
			if(pre[U[i]]<=mid&&pre[V[i]]<=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) {
	for(int i=0;i<U.size();++i){
		adj1[U[i]].eb(V[i]);
		adj1[V[i]].eb(U[i]);
	}
	tmp.assign((int)U.size(),0);
	dist=ask(tmp);
	play(N,U,V,play(N,U,V,0));
	answer(ans[0],ans[1]);
}

Compilation message

highway.cpp: In function 'int play(int, std::vector<int>&, std::vector<int>&, int)':
highway.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid=l+r>>1;
      |           ~^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:51:15: 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){
      |              ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 14 ms 3868 KB Output is correct
3 Correct 101 ms 8468 KB Output is correct
4 Correct 103 ms 8244 KB Output is correct
5 Correct 118 ms 8812 KB Output is correct
6 Correct 107 ms 8456 KB Output is correct
7 Correct 105 ms 8940 KB Output is correct
8 Correct 131 ms 8732 KB Output is correct
9 Correct 94 ms 8472 KB Output is correct
10 Correct 102 ms 8004 KB Output is correct
11 Correct 109 ms 8308 KB Output is correct
12 Correct 134 ms 8552 KB Output is correct
13 Correct 98 ms 8080 KB Output is correct
14 Incorrect 117 ms 8120 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 8 ms 3852 KB Output is correct
2 Correct 16 ms 4200 KB Output is correct
3 Correct 26 ms 4748 KB Output is correct
4 Correct 66 ms 8092 KB Output is correct
5 Correct 82 ms 7836 KB Output is correct
6 Correct 92 ms 7848 KB Output is correct
7 Correct 68 ms 7868 KB Output is correct
8 Correct 68 ms 7848 KB Output is correct
9 Incorrect 77 ms 8064 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 1 ms 3144 KB Output is correct
2 Correct 16 ms 3864 KB Output is correct
3 Correct 66 ms 7436 KB Output is correct
4 Correct 101 ms 8216 KB Output is correct
5 Correct 91 ms 8220 KB Output is correct
6 Correct 118 ms 8484 KB Output is correct
7 Correct 95 ms 8456 KB Output is correct
8 Correct 99 ms 8464 KB Output is correct
9 Incorrect 81 ms 7992 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 14 ms 3884 KB Output is correct
2 Correct 16 ms 3664 KB Output is correct
3 Correct 137 ms 8712 KB Output is correct
4 Correct 116 ms 9404 KB Output is correct
5 Correct 154 ms 9936 KB Output is correct
6 Correct 125 ms 9464 KB Output is correct
7 Correct 146 ms 9928 KB Output is correct
8 Incorrect 138 ms 9484 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 18 ms 3880 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -