oj.uz

Submission #933843

# Submission time Handle Problem Language Result Execution time Memory
933843 2024-02-26T11:43:30 Z kim Highway Tolls (IOI18_highway) C++17
51 / 100
 154 ms 14588 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second
 
using ti3=tuple<int,int,int>;
 
vector<int> adj1[90005],adj2[90005];
bitset<90005> vis;
int pre[90005];
 
vector<int> ans,tmp;
ll dist;
int play(int n,vector<int> &U,vector<int> &V,int u0){
	for(int i=0;i<n;++i) adj2[i].clear();
	vis=0;
	int m=U.size();
	{
		queue<int> q;
		q.emplace(u0);
		vis[u0]=1;
		while(q.size()){
			int u=q.front(); q.pop();
			for(auto &v:adj1[u]){
				if(vis[v]) continue;
				vis[v]=1;
				q.emplace(v);
				adj2[u].eb(v);
				adj2[v].eb(u);
			}
		}
	}
	{
		stack<pii> st;
		st.emplace(u0,u0);
		int id=-1;
		while(st.size()){
			auto [u,p]=st.top(); st.pop();
			pre[u]=++id;
			for(auto &v:adj2[u]){
				if(v!=p) st.emplace(v,u);
			}
		}
	}
	int l=0,r=n-1;
	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;
	}
	cerr<<pre[0]<<" "<<pre[1]<<" "<<pre[2]<<" "<<pre[3]<<'\n';
	for(int i=0;i<n;++i){
		if(pre[i]==l){
			ans.eb(i);
			return i;
		}
	}
}
 
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:51:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |   int mid=l+r>>1;
      |           ~^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i=0;i<U.size();++i){
      |              ~^~~~~~~~~
highway.cpp: In function 'int play(int, std::vector<int>&, std::vector<int>&, int)':
highway.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4916 KB Output is correct
2 Correct 13 ms 5776 KB Output is correct
3 Correct 129 ms 12928 KB Output is correct
4 Correct 125 ms 12916 KB Output is correct
5 Correct 112 ms 12920 KB Output is correct
6 Correct 126 ms 13604 KB Output is correct
7 Correct 146 ms 13104 KB Output is correct
8 Correct 149 ms 12868 KB Output is correct
9 Correct 127 ms 13112 KB Output is correct
10 Correct 132 ms 12904 KB Output is correct
11 Correct 132 ms 13136 KB Output is correct
12 Correct 132 ms 12436 KB Output is correct
13 Correct 127 ms 13128 KB Output is correct
14 Correct 121 ms 13132 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5708 KB Output is correct
2 Correct 20 ms 6588 KB Output is correct
3 Correct 40 ms 7784 KB Output is correct
4 Correct 70 ms 12680 KB Output is correct
5 Correct 69 ms 12436 KB Output is correct
6 Correct 100 ms 12448 KB Output is correct
7 Correct 101 ms 12432 KB Output is correct
8 Correct 74 ms 12676 KB Output is correct
9 Correct 77 ms 12924 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4912 KB Output is correct
2 Correct 17 ms 5744 KB Output is correct
3 Correct 94 ms 11100 KB Output is correct
4 Correct 121 ms 13160 KB Output is correct
5 Correct 134 ms 13112 KB Output is correct
6 Correct 101 ms 13104 KB Output is correct
7 Correct 123 ms 13168 KB Output is correct
8 Correct 109 ms 12896 KB Output is correct
9 Correct 113 ms 13348 KB Output is correct
10 Correct 154 ms 12916 KB Output is correct
11 Correct 142 ms 12900 KB Output is correct
12 Correct 114 ms 12680 KB Output is correct
13 Correct 118 ms 13140 KB Output is correct
14 Correct 113 ms 12672 KB Output is correct
15 Correct 99 ms 12876 KB Output is correct
16 Correct 95 ms 12688 KB Output is correct
17 Correct 122 ms 12900 KB Output is correct
18 Correct 94 ms 12664 KB Output is correct
19 Correct 101 ms 12680 KB Output is correct
20 Correct 109 ms 12900 KB Output is correct
21 Correct 90 ms 14128 KB Output is correct
22 Correct 90 ms 14588 KB Output is correct
23 Correct 100 ms 14408 KB Output is correct
24 Correct 113 ms 13912 KB Output is correct
25 Correct 137 ms 12840 KB Output is correct

Subtask #5
0 / 18.0

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