oj.uz

답안 #1068212

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068212 2024-08-21T08:35:18 Z Faisal_Saqib 통행료 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 221 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -