oj.uz

답안 #1068262

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068262 2024-08-21T08:54:08 Z Muhammad_Aneeq 통행료 (IOI18_highway) C++17
51 / 100
 135 ms 37860 KB 
#include <vector>
#include <iostream>
#include <map>
#include "highway.h"
using namespace std;
int const MAXN=1e5;
vector<int>w;
long long dis=0;
vector<pair<int,int>>nei[MAXN]={};
int B1,A1;
vector<pair<int,int>>edges;
vector<int>ed[MAXN]={};
int h[MAXN]={};
int p[MAXN]={};
vector<int>d;
vector<int>g;
int it[MAXN],ot[MAXN];
int tm=0;
map<vector<int>,long long>vis;
long long ask1(vector<int>w)
{
	if (vis.find(w)==vis.end())
		vis[w]=ask(w);
	return vis[w];
}
void dfs(int u,int pa=-1)
{
	it[u]=tm++;
	p[u]=pa;
	for (auto [i,in]:nei[u])
	{
		if (i==pa)
			continue;
		ed[h[u]].push_back(in);
		h[i]=h[u]+1;
		dfs(i,u);
	}
	ot[u]=tm-1;
}
bool check(int mid)
{
	for (int i=mid;i<MAXN;i++)
	{
		for (auto j:ed[i])
			w[j]=1;
	}
	long long g=ask1(w);
	for (int i=mid;i<MAXN;i++)
	{
		for (auto j:ed[i])
			w[j]=0;
	}
	return (g!=dis);
}
bool check1(int mid,int z)
{
	for (int i=mid;i<MAXN;i++)
	{
		for (auto j:ed[i])
		{
			w[j]=1;
		}
	}
	long long g=ask1(w);
	for (int i=mid;i<MAXN;i++)
	{
		for (auto j:ed[i])
			w[j]=0;
	}
	return (g!=dis);	
}
void divi1(int st,int en,int cnt)
{
	if (st==en)
	{
		d.push_back(g[en]);
		return;
	}
	int mid=(st+en)/2;
	for (int i=st;i<=mid;i++)
		w[g[i]]=1;
	long long cos=ask1(w);
	for (int i=st;i<=mid;i++)
		w[g[i]]=0;
	int f=(cos-dis)/(B1-A1);
	if (f)
		divi1(st,mid,f);
	if (cnt-f)
		divi1(mid+1,en,cnt-f);
}
void divi(int st,int en)
{
	for (auto i:g)
		w[i]=1;
	long long co=ask1(w);
	for (auto i:g)
		w[i]=0;
	divi1(st,en,(co-dis)/(B1-A1));
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
	A1=A,B1=B;
	int m=U.size();
	for (int i=0;i<m;i++)
	{
		nei[U[i]].push_back({V[i],i});
		nei[V[i]].push_back({U[i],i});
	}
	dfs(0);
	for (int i=0;i<m;i++)
	{
		if (h[U[i]]>h[V[i]])
			swap(U[i],V[i]);
		edges.push_back({U[i],V[i]});
	}
	w.resize(m,0);
	dis=ask1(w);
	h[0]=0;
	int st=0,en=N;
	while (st+1<en)
	{
		int mid=(st+en)/2;
		if (check(mid))
			st=mid;
		else
			en=mid;
	}
	for (auto i:ed[st])
		g.push_back(i);
	divi(0,g.size()-1);
	if (d.size()==2)
		answer(edges[d[0]].second,edges[d[1]].second);
	else
	{
		en=st;
		st=-1;
		int z=edges[d[0]].second;
		int q=z;
		while (q)
		{
			vector<int>g;
			for (auto i:ed[h[q]-1])
			{
				if (edges[i].second==q)
					continue;
				g.push_back(i);
			}
			ed[h[q]-1]=g;
			q=p[q];
		}
		while (st+1<en)
		{
			int mid=(st+en)/2;
			if (check1(mid,z))
				st=mid;
			else
				en=mid;
		}
		if (st==-1)
		{
			int len=dis/A;
			int x=z;
			while (len--)
				x=p[x];
			answer(z,x);
			return;
		}
		d={};
		g={};
		for (auto i:ed[st])
			g.push_back(i);
		divi(0,g.size()-1);
		answer(z,edges[d[0]].second);
	}
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 5 ms 5012 KB Output is correct
5 Correct 3 ms 4952 KB Output is correct
6 Correct 4 ms 5060 KB Output is correct
7 Correct 4 ms 4952 KB Output is correct
8 Correct 3 ms 4952 KB Output is correct
9 Correct 4 ms 4952 KB Output is correct
10 Correct 4 ms 4952 KB Output is correct
11 Correct 4 ms 4952 KB Output is correct
12 Correct 4 ms 4952 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5208 KB Output is correct
2 Correct 15 ms 6744 KB Output is correct
3 Correct 98 ms 21900 KB Output is correct
4 Correct 100 ms 21956 KB Output is correct
5 Correct 93 ms 22768 KB Output is correct
6 Correct 103 ms 21508 KB Output is correct
7 Correct 91 ms 21012 KB Output is correct
8 Correct 94 ms 21916 KB Output is correct
9 Correct 95 ms 21040 KB Output is correct
10 Correct 95 ms 21960 KB Output is correct
11 Correct 105 ms 25892 KB Output is correct
12 Correct 125 ms 26724 KB Output is correct
13 Correct 102 ms 26928 KB Output is correct
14 Correct 109 ms 25224 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 7768 KB Output is correct
2 Correct 21 ms 10484 KB Output is correct
3 Correct 35 ms 13008 KB Output is correct
4 Correct 99 ms 29628 KB Output is correct
5 Correct 90 ms 29680 KB Output is correct
6 Correct 106 ms 29964 KB Output is correct
7 Correct 108 ms 29996 KB Output is correct
8 Correct 102 ms 30024 KB Output is correct
9 Correct 118 ms 30092 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5208 KB Output is correct
2 Correct 14 ms 7032 KB Output is correct
3 Correct 71 ms 17984 KB Output is correct
4 Correct 107 ms 27764 KB Output is correct
5 Correct 98 ms 21752 KB Output is correct
6 Correct 111 ms 28080 KB Output is correct
7 Correct 89 ms 21948 KB Output is correct
8 Correct 113 ms 22404 KB Output is correct
9 Correct 109 ms 27368 KB Output is correct
10 Correct 108 ms 27988 KB Output is correct
11 Correct 115 ms 27720 KB Output is correct
12 Correct 108 ms 28896 KB Output is correct
13 Correct 121 ms 26612 KB Output is correct
14 Correct 127 ms 28136 KB Output is correct
15 Correct 103 ms 26948 KB Output is correct
16 Correct 103 ms 21308 KB Output is correct
17 Correct 116 ms 29184 KB Output is correct
18 Correct 112 ms 27556 KB Output is correct
19 Correct 103 ms 26816 KB Output is correct
20 Correct 111 ms 28680 KB Output is correct
21 Correct 102 ms 25880 KB Output is correct
22 Correct 116 ms 26140 KB Output is correct
23 Correct 114 ms 27844 KB Output is correct
24 Correct 125 ms 29376 KB Output is correct
25 Correct 135 ms 37860 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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