oj.uz

Submission #137821

# Submission time Handle Problem Language Result Execution time Memory
137821 2019-07-28T09:59:43 Z bensonlzl Highway Tolls (IOI18_highway) C++14
51 / 100
 372 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pi;
typedef long long ll;

vector<pi> AdjList[100005];
vector<int> Ax;
vector<pi> EdgeList;

ll bigA, bigB, bigN, bigM, dist, dsu, dtv, S, T;

void res_Ax(){
	for (int i = 0; i < bigM; ++i) Ax[i] = 0;
}

int find_spath_edge(vector<int> ved0, vector<int> ved1){
	//cout << ved0.size() << ' ' << ved1.size() << '\n';
	vector<int> v0, v1;
	if (ved0.size() == 1 && ved1.size() == 0){
		return ved0[0];
	}
	else if (ved0.size() == 0 && ved1.size() == 1){
		return ved1[0];
	}
	res_Ax();
	for (int i = 0; i < ved1.size(); ++i){
		Ax[ved1[i]] = 1;
	}
	ll nd = ask(Ax);
	if (nd > dist){
		for (int i = 0; i < ved1.size(); ++i){
			if (i%2==0) v0.push_back(ved1[i]);
			else v1.push_back(ved1[i]);
		}
	}
	else{
		for (int i = 0; i < ved0.size(); ++i){
			if (i%2==0) v0.push_back(ved0[i]);
			else v1.push_back(ved0[i]);
		}
	}
	return find_spath_edge(v0,v1);
}

vector<int> tree_u_edges, tree_v_edges;

void dfs(int p, int x, int c){
	for (auto it : AdjList[x]){
		if (it.second == p) continue;
		if (c == 0) tree_u_edges.push_back(it.first);
		else tree_v_edges.push_back(it.first);
		dfs(x,it.second,c);
	}
}

vector<pi> pot_edges;

void dfs2(int p, int x, int d){
	if (d == 0) return;
	for (auto it : AdjList[x]){
		if (it.second == p) continue;
		if (d == 1){
			pot_edges.push_back(pi(it.first,it.second));
		}
		else{
			dfs2(x,it.second,d-1);
		}
	}

}

int solve(vector<int> tree_ed, int source, int parent, int distance){
	pot_edges.clear();
	dfs2(parent,source,distance);
	assert(pot_edges.size() > 0);
	vector<int> v0, v1;
	for (int i = 0; i < pot_edges.size(); ++i){
		if (i%2==0) v0.push_back(pot_edges[i].first);
		else v1.push_back(pot_edges[i].first);
	}
	int e = find_spath_edge(v0,v1);
	for (int i = 0; i < pot_edges.size(); ++i){
		if (pot_edges[i].first == e) return pot_edges[i].second;
	}
	assert(0);
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	bigM = U.size(); bigN = N; bigA = A; bigB = B;
	Ax.resize(bigM,0);
	dist = ask(Ax);
	for (int i = 0; i < bigM; ++i){
		AdjList[U[i]].push_back(pi(i,V[i]));
		AdjList[V[i]].push_back(pi(i,U[i]));
		EdgeList.push_back(pi(U[i],V[i]));
	}
	vector<int> v0, v1;
	for (int i = 0; i < bigM; ++i){
		if (i%2==0){
			v0.push_back(i);
		}
		else v1.push_back(i);
	}
	res_Ax();
	int x = find_spath_edge(v0,v1);
	int u = EdgeList[x].first, v = EdgeList[x].second;
	dfs(v,u,0); dfs(u,v,1);
	//cout << u << ' ' << v << '\n' << flush;
	res_Ax();
	for (int i = 0; i < tree_u_edges.size(); ++i){
		Ax[tree_u_edges[i]] = 1;
	}
	dsu = (ask(Ax)-dist)/(B-A);
	dtv = dist/A - dsu - 1;
	assert(dsu >= 0 && dtv >= 0);
	//cout << dsu << ' ' << dtv << '\n' << flush;
	if (dsu > 0) S = solve(tree_u_edges,u,v,dsu);
	else S = u;
	//cout << S << '\n' << flush;
	if (dtv > 0 ) T = solve(tree_v_edges,v,u,dtv);
	else T = v;
	//assert(0);
	answer(S,T);
}

Compilation message

highway.cpp: In function 'int find_spath_edge(std::vector<int>, std::vector<int>)':
highway.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ved1.size(); ++i){
                  ~~^~~~~~~~~~~~~
highway.cpp:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < ved1.size(); ++i){
                   ~~^~~~~~~~~~~~~
highway.cpp:40:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < ved0.size(); ++i){
                   ~~^~~~~~~~~~~~~
highway.cpp: In function 'int solve(std::vector<int>, int, int, int)':
highway.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < pot_edges.size(); ++i){
                  ~~^~~~~~~~~~~~~~~~~~
highway.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < pot_edges.size(); ++i){
                  ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:113:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < tree_u_edges.size(); ++i){
                  ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2552 KB Output is correct
2 Correct 4 ms 2668 KB Output is correct
3 Correct 4 ms 2668 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 3 ms 2680 KB Output is correct
7 Correct 4 ms 2660 KB Output is correct
8 Correct 4 ms 2668 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 4 ms 2680 KB Output is correct
12 Correct 4 ms 2696 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2764 KB Output is correct
2 Correct 15 ms 3512 KB Output is correct
3 Correct 184 ms 10344 KB Output is correct
4 Correct 193 ms 10300 KB Output is correct
5 Correct 173 ms 10332 KB Output is correct
6 Correct 200 ms 10324 KB Output is correct
7 Correct 196 ms 10036 KB Output is correct
8 Correct 197 ms 10340 KB Output is correct
9 Correct 195 ms 10348 KB Output is correct
10 Correct 184 ms 10280 KB Output is correct
11 Correct 181 ms 10856 KB Output is correct
12 Correct 164 ms 11612 KB Output is correct
13 Correct 171 ms 10904 KB Output is correct
14 Correct 210 ms 10892 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3968 KB Output is correct
2 Correct 39 ms 5144 KB Output is correct
3 Correct 87 ms 6500 KB Output is correct
4 Correct 132 ms 12564 KB Output is correct
5 Correct 136 ms 13068 KB Output is correct
6 Correct 154 ms 13576 KB Output is correct
7 Correct 165 ms 14888 KB Output is correct
8 Correct 124 ms 13096 KB Output is correct
9 Correct 149 ms 13828 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 21 ms 3512 KB Output is correct
3 Correct 105 ms 8536 KB Output is correct
4 Correct 135 ms 10228 KB Output is correct
5 Correct 181 ms 10108 KB Output is correct
6 Correct 163 ms 10352 KB Output is correct
7 Correct 187 ms 10280 KB Output is correct
8 Correct 181 ms 10228 KB Output is correct
9 Correct 180 ms 10472 KB Output is correct
10 Correct 137 ms 10348 KB Output is correct
11 Correct 186 ms 10892 KB Output is correct
12 Correct 172 ms 11832 KB Output is correct
13 Correct 189 ms 10656 KB Output is correct
14 Correct 161 ms 11136 KB Output is correct
15 Correct 173 ms 10292 KB Output is correct
16 Correct 184 ms 10232 KB Output is correct
17 Correct 158 ms 10744 KB Output is correct
18 Correct 187 ms 11268 KB Output is correct
19 Correct 193 ms 10284 KB Output is correct
20 Correct 193 ms 11672 KB Output is correct
21 Correct 180 ms 12244 KB Output is correct
22 Correct 167 ms 12360 KB Output is correct
23 Correct 191 ms 11100 KB Output is correct
24 Correct 224 ms 11288 KB Output is correct
25 Correct 223 ms 14052 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 372 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 321 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -