oj.uz

Submission #933821

# Submission time Handle Problem Language Result Execution time Memory
933821 2024-02-26T11:17:40 Z kim Highway Tolls (IOI18_highway) C++17
5 / 100
 150 ms 13576 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],adj2[90005];
bitset<90005> vis;
int pre[90005];

vector<int> ans,tmp;
int 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:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int mid=l+r>>1;
      |           ~^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i=0;i<U.size();++i){
      |              ~^~~~~~~~~
highway.cpp: In function 'int play(int, std::vector<int>&, std::vector<int>&, int)':
highway.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
   65 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4868 KB Output is correct
2 Correct 2 ms 5120 KB Output is correct
3 Correct 2 ms 4868 KB Output is correct
4 Correct 1 ms 4864 KB Output is correct
5 Correct 1 ms 5124 KB Output is correct
6 Correct 1 ms 4864 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 4864 KB Output is correct
10 Correct 1 ms 4872 KB Output is correct
11 Correct 1 ms 4868 KB Output is correct
12 Correct 1 ms 4864 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4912 KB Output is correct
2 Correct 11 ms 5784 KB Output is correct
3 Correct 145 ms 12960 KB Output is correct
4 Correct 119 ms 13156 KB Output is correct
5 Correct 143 ms 12884 KB Output is correct
6 Correct 117 ms 13156 KB Output is correct
7 Correct 105 ms 13576 KB Output is correct
8 Correct 150 ms 12680 KB Output is correct
9 Correct 116 ms 13416 KB Output is correct
10 Correct 136 ms 12676 KB Output is correct
11 Correct 95 ms 12660 KB Output is correct
12 Correct 129 ms 12896 KB Output is correct
13 Correct 144 ms 12884 KB Output is correct
14 Incorrect 96 ms 12432 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 10 ms 5740 KB Output is correct
2 Correct 17 ms 6592 KB Output is correct
3 Correct 29 ms 7648 KB Output is correct
4 Correct 116 ms 12504 KB Output is correct
5 Correct 73 ms 12884 KB Output is correct
6 Correct 76 ms 12704 KB Output is correct
7 Correct 72 ms 12444 KB Output is correct
8 Correct 127 ms 12696 KB Output is correct
9 Incorrect 113 ms 12452 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 4916 KB Output is correct
2 Correct 15 ms 5760 KB Output is correct
3 Correct 77 ms 10996 KB Output is correct
4 Correct 114 ms 12668 KB Output is correct
5 Correct 95 ms 13176 KB Output is correct
6 Correct 139 ms 12908 KB Output is correct
7 Correct 129 ms 12932 KB Output is correct
8 Correct 107 ms 13120 KB Output is correct
9 Incorrect 108 ms 12668 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 Incorrect 18 ms 5804 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 -