oj.uz

Submission #621041

# Submission time Handle Problem Language Result Execution time Memory
621041 2022-08-03T11:23:51 Z MeGustaElArroz23 Highway Tolls (IOI18_highway) C++14
51 / 100
 163 ms 23024 KB 
#include "highway.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
//#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define vvii vector<vii>
#define vb vector<bool>

#define fi first
#define se second
#define pb push_back

#define piii pair<pii,int>
#define viii vector<piii>

int n;
int m;
ll a;
ll b;
ll dist;

vi u;
vi v;

int myask(vi h){
	vi toask(m,0);
	for (int x:h) toask[x]=1;
	ll ans=ask(toask);
	ans-=a*dist;
	return ans/(b-a);
}

vector<vector<piii>> withprof;

vvii conexiones;

void dfs1(int ac, int ant, int prof){
	for (pii y:conexiones[ac]){
		if (y.fi!=ant){
			withprof[prof].pb(piii{pii{ac,y.fi},y.se}); //up down id
			dfs1(y.fi,ac,prof+1);
		}
	}
}

vii sussy;

void dfs2(int ac, int ant, int acdis){
	for (pii y:conexiones[ac]){
		if (y.fi!=ant){
			if (acdis==dist-1) sussy.pb(y);
			dfs2(y.fi,ac,acdis+1);
		}
	}
}

void find_pair(int N, vi U, vi V, int A, int B) {
	n=N; m=U.size(); a=A; b=B; u=U; v=V;
	dist=ask(vi(m,0))/a;

	//cerr << "A";
	conexiones=vvii(n);
	for (int i=0;i<m;i++){
		conexiones[u[i]].pb(pii{v[i],i});
		conexiones[v[i]].pb(pii{u[i],i});
	}
	//cerr << "A";

	withprof=vector<vector<piii>>(n);

	//cerr << "A";
	dfs1(0,-1,0);
	//cerr << "A";

	int l=0;
	int r=n;
	while (l!=r-1){
		int mid=(l+r)/2;
		vi toadd;
		for (int prof=mid;prof<n-1;prof++){
			for (piii x:withprof[prof]) toadd.pb(x.se);
		}
		if (myask(toadd)>0) l=mid;
		else r=mid;
	}

	//cerr << "A";

	viii sus=withprof[l];

	while (sus.size()>1){
		viii sus1;
		viii sus2;
		for (int i=0;i<sus.size();i++){
			if (i%2) sus1.pb(sus[i]);
			else sus2.pb(sus[i]);
		}
		vi toadd;
		for (piii x:sus1) toadd.pb(x.se);
		if (myask(toadd)) sus=sus1;
		else sus=sus2;
	}

	//cerr << "A";

	int sol1=sus[0].fi.se;

	dfs2(sol1,-1,0);

	//cerr << "A";

	while (sussy.size()>1){
		vii sussy1;
		vii sussy2;
		for (int i=0;i<sussy.size();i++){
			if (i%2) sussy1.pb(sussy[i]);
			else sussy2.pb(sussy[i]);
		}
		vi toadd;
		for (pii x:sussy1) toadd.pb(x.se);
		if (myask(toadd)) sussy=sussy1;
		else sussy=sussy2;
	}

	//cerr << "A";

	int sol2=sussy[0].fi;

	answer(sol1,sol2);

}

// N M A B S T
// U[i] V[i]

/* 
4 3 1 3 1 3
0 1 
 
0 3 
1 2
*/

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:100:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for (int i=0;i<sus.size();i++){
      |                ~^~~~~~~~~~~
highway.cpp:121:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   for (int i=0;i<sussy.size();i++){
      |                ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 0 ms 208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 9 ms 1800 KB Output is correct
3 Correct 131 ms 12280 KB Output is correct
4 Correct 114 ms 12328 KB Output is correct
5 Correct 150 ms 12864 KB Output is correct
6 Correct 139 ms 12372 KB Output is correct
7 Correct 141 ms 12968 KB Output is correct
8 Correct 140 ms 12584 KB Output is correct
9 Correct 145 ms 12644 KB Output is correct
10 Correct 150 ms 12548 KB Output is correct
11 Correct 151 ms 14792 KB Output is correct
12 Correct 119 ms 15708 KB Output is correct
13 Correct 116 ms 14896 KB Output is correct
14 Correct 111 ms 13608 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2896 KB Output is correct
2 Correct 21 ms 5372 KB Output is correct
3 Correct 37 ms 7756 KB Output is correct
4 Correct 93 ms 22932 KB Output is correct
5 Correct 114 ms 23024 KB Output is correct
6 Correct 125 ms 22932 KB Output is correct
7 Correct 126 ms 22896 KB Output is correct
8 Correct 98 ms 22908 KB Output is correct
9 Correct 115 ms 23016 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 12 ms 1652 KB Output is correct
3 Correct 79 ms 9948 KB Output is correct
4 Correct 159 ms 12412 KB Output is correct
5 Correct 110 ms 12540 KB Output is correct
6 Correct 104 ms 12564 KB Output is correct
7 Correct 140 ms 12604 KB Output is correct
8 Correct 121 ms 12640 KB Output is correct
9 Correct 112 ms 12436 KB Output is correct
10 Correct 149 ms 12632 KB Output is correct
11 Correct 145 ms 13524 KB Output is correct
12 Correct 163 ms 15844 KB Output is correct
13 Correct 107 ms 14692 KB Output is correct
14 Correct 155 ms 15648 KB Output is correct
15 Correct 128 ms 12660 KB Output is correct
16 Correct 96 ms 12528 KB Output is correct
17 Correct 150 ms 14952 KB Output is correct
18 Correct 152 ms 14500 KB Output is correct
19 Correct 144 ms 12596 KB Output is correct
20 Correct 114 ms 16188 KB Output is correct
21 Correct 142 ms 14912 KB Output is correct
22 Correct 136 ms 14916 KB Output is correct
23 Correct 103 ms 13268 KB Output is correct
24 Correct 109 ms 14400 KB Output is correct
25 Correct 134 ms 20988 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 5812 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 6260 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -