oj.uz

Submission #1068212

# Submission time Handle Problem Language Result Execution time Memory
1068212 2024-08-21T08:35:18 Z Faisal_Saqib Highway Tolls (IOI18_highway) C++17
12 / 100
 221 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
long long ask(const std::vector<int> &w);
void answer(int s, int t);
const ll NP=1e5;
vector<pair<ll,ll>> ma[NP],tmp;
vector<int> w;
ll mi,a,b,par[NP],vis[NP];
ll wantd;
vector<int> ans;
void dfs(int x,int p=-1,ll d=0)
{
	par[x]=p;
	if(d==(wantd))
		ans.pb(x);
	for(auto y:ma[x])
	{
		if(y.second!=p)
		{
			dfs(y.second,x,d+1);
		}
	}
}
map<pair<int,int>,int> edg;
void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B)
{
	int m=u.size();
	w.resize(m,0);
	a=A;
	b=B;
	mi=ask(w);
	wantd=(mi/a);
	for(int i=0;i<n;i++)
		ma[i].clear();
	for(int i=0;i<m;i++)
	{
		edg[{u[i],v[i]}]=i;
		edg[{v[i],u[i]}]=i;
		ma[u[i]].pb({i,v[i]});
		ma[v[i]].pb({i,u[i]});
	}
	dfs(0);
	int s=-1;
	int e=ans.size();
	while(s+1<e)
	{
		int mid=(s+e)/2;
		for(int i=0;i<n;i++)
			vis[i]=0;
		vector<int> cur;
		for(int j=s+1;j<=mid;j++)
		{
			int s=ans[j];
			while(s!=0)
			{
				if(vis[s])break;
				vis[s]=1;
				cur.push_back(edg[{s,par[s]}]);
				s=par[s];
			}
		}
		for(auto i:cur)
			w[i]=1;
		ll wa=ask(w);
		for(auto i:cur)
			w[i]=0;
		if(wa==(b*wantd))
		{
			e=mid;
		}
		else
		{
			s=mid;
		}
	}
	answer(0,ans[e]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 2 ms 2788 KB Output is correct
10 Correct 2 ms 2648 KB Output is correct
11 Correct 1 ms 4436 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 13 ms 4912 KB Output is correct
3 Correct 176 ms 21932 KB Output is correct
4 Correct 168 ms 22096 KB Output is correct
5 Correct 165 ms 22032 KB Output is correct
6 Correct 168 ms 22076 KB Output is correct
7 Correct 164 ms 22020 KB Output is correct
8 Correct 171 ms 22020 KB Output is correct
9 Correct 140 ms 22020 KB Output is correct
10 Correct 158 ms 22016 KB Output is correct
11 Correct 172 ms 23512 KB Output is correct
12 Correct 163 ms 23900 KB Output is correct
13 Correct 167 ms 23632 KB Output is correct
14 Correct 165 ms 23044 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 207 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 221 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -