Submission #123243

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
123243	2019-06-30T16:15:14 Z	imyujin	Highway design (CEOI12_highway)	C++14	Compilation error	0 ms	0 KB

highway

#include "highway.h"
#include<vector>
#include<queue>
#include<bitset>

using namespace std;

#define MAXN 90005

typedef pair<int, int> pii;

int N, M, A, B;
int d, se;
vector<pii> ed[MAXN];
int da[MAXN], db[MAXN];
bitset<MAXN> chk;
int num[MAXN];

void bfs(int x, int dx[]) {
	queue<int> q;

	for(int i = 0; i < N; i++) dx[i] = -1;
	dx[x] = 0;
	q.push(x);
	while(!q.empty()) {
		int t = q.front();
		q.pop();
		for(auto a : ed[t]) if(dx[a.first] == -1) {
			dx[a.first] = dx[t] + 1;
			q.push(a.first);
		}
	}
}

int f(int x, int dx[], int dy[]) {
	queue<int> q;
	vector<int> con;

	for(int i = 0; i < N; i++) chk[i] = false;
	q.push(x);
	chk[x] = true;
	while(!q.empty()) {
		int t = q.front();
		q.pop();
		con.push_back(t);
		for(auto a : ed[t]) if(dx[a.first] < dy[a.first] && !chk[a.first]) {
			chk[a.first] = true;
			q.push(a.first);
		}
	}

	for(int i = 0; i < N; i++) num[i] = -1;
	for(int i = 0; i < con.size(); i++) num[con[i]] = i;

	/*
	for(auto a : con) printf("%d ", a);
	printf("\n");
	*/

	vector<int> w(M, 0);
	int s = 0, e = con.size() - 1;
	int m = s + e >> 1;
	for(int i = m + 1; i <= e; i++) for(auto a : ed[con[i]]) w[a.second] = 1;
	while(s < e) {
		//printf("s = %d, e = %d\n", s, e);
		if(ask(w) == d * A) {
			e = m;
			m = s + e >> 1;
			for(int i = m + 1; i <= e; i++) for(auto a : ed[con[i]]) w[a.second] = 1;
		}
		else {
			s = m + 1;
			m = s + e >> 1;
			for(int i = s + 1; i <= m; i++) for(auto a : ed[con[i]]) if(num[a.first] < i) w[a.second] = 0;
		}
	}
	return con[s];
}

void find_pair(int n, vector<int> U, vector<int> V, int a, int b) {
	N = n;
	M = U.size();
	A = a;
	B = b;
	vector<int> w(M, 0);

	for(int i = 0; i < M; i++) {
		ed[U[i]].push_back(make_pair(V[i], i));
		ed[V[i]].push_back(make_pair(U[i], i));
	}

	d = ask(w) / A;
	int s = 0, e = M - 1, m = N - 1 >> 1;
	for(int i = m + 1; i <= e; i++) w[i] = 1;
	while(s < e) {
		if(ask(w) != A * d) {
			s = m + 1;
			m = s + e >> 1;
			for(int i = s; i <= m; i++) w[i] = 0;
		}
		else {
			e = m;
			m = s + e >> 1;
			for(int i = m + 1; i <= e; i++) w[i] = 1;
		}
	}
	se = s;


	int alpha = U[se], beta = V[se];
	//printf("se=%d(%d, %d)\n", se, alpha, beta);
	bfs(alpha, da);
	bfs(beta, db);
	//for(int i = 0; i < N; i++) printf("[%d %d]\n", da[i], db[i]);
	answer(f(alpha, da, db), f(beta, db, da));
}

Compilation message

highway.cpp:1:10: fatal error: highway.h: No such file or directory
 #include "highway.h"
          ^~~~~~~~~~~
compilation terminated.
office.c: In function 'int isOnLine(int, int, int)':
office.c:85:29: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
     _Fin(0, "Protocol error");
                             ^
office.c:88:29: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
     _Fin(0, "Protocol error");
                             ^
office.c:92:37: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
     _Fin(false, "Too many questions");
                                     ^
office.c:83:7: warning: unused variable 'i' [-Wunused-variable]
   int i;
       ^
office.c: In function 'void Answer(int, int, int, int)':
office.c:123:29: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
     _Fin(0, "Protocol error");
                             ^
office.c:128:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if( (-_Apa[na1]==_N-3) && (na2!=na1) && (nb2!=na1) ||
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
office.c:130:30: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
          _Fin(true, "Correct");
                              ^
office.c:132:36: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
          _Fin(false, "Wrong answer");
                                    ^
office.c:134:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if( (-_Apa[na2]==_N-3) && (na1!=na2) && (nb1!=na2) ||
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
office.c:136:30: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
          _Fin(true, "Correct");
                              ^
office.c:138:36: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
          _Fin(false, "Wrong answer");
                                    ^
office.c:140:33: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
       _Fin(false, "Wrong answer");
                                 ^
office.c:142:23: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings]
   _Fin(true, "Correct");
                       ^
office.c:120:27: warning: unused variable 'pont' [-Wunused-variable]
   int na1, nb1, na2, nb2, pont;
                           ^~~~
office.c: In function 'void _doInit()':
office.c:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &_N);
     ~~~~~^~~~~~~~~~~