제출 #137821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137821		bensonlzl	통행료 (IOI18_highway)	C++14	51 / 100	372 ms	262148 KiB

highway

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31