oj.uz

Submission #123887

# Submission time Handle Problem Language Result Execution time Memory
123887 2019-07-02T08:35:57 Z 임유진(#3031) Meetings (JOI19_meetings) C++14
0 / 100
 136 ms 864 KB 
#include "meetings.h"
#include<vector>
#include<algorithm>
#include<bitset>

using namespace std;

#define MAXN 2005

int res[MAXN][MAXN];
int cmpc;
vector<int> X[MAXN];
bitset<MAXN> chk;

bool cmp(int a, int b) {
	if(res[a][b] != 0) return res[a][b] == 1;
	if(res[b][a] != 0) return res[b][a] == 1;
	if(Query(cmpc, a, b) == a) {
		res[a][b] = 1;
		res[b][a] = -1;
		return true;
	}
	else {
		res[a][b] = -1;
		res[b][a] = 1;
		return false;
	}
}

void brid(int a, int b) {
	Bridge(min(a, b), max(a, b));
}

void f(vector<int> v) {
	/*
	printf("f(v = [");
	for(auto a : v) printf("%d ", a);
	printf("])\n");
	*/

	if(v.size() <= 1) return;
	if(v.size() == 2) {
		brid(v[0], v[1]);
		return;
	}

	random_shuffle(v.begin(), v.end());

	vector<int> L;
	int alpha = v[0], beta = v[1];
	for(auto a : v) {
		X[a].clear();
		chk[a] = false;
	}
	for(int i = 2; i < v.size(); i++) {
		int t = Query(alpha, beta, v[i]);
		//printf("alpha = %d, beta = %d, v[i] = %d, t = %d\n", alpha, beta, v[i], t);
		if(t == alpha) {
			L.push_back(alpha);
			X[alpha].push_back(alpha);
			alpha = v[i];
		}
		else if(t == beta) {
			L.push_back(beta);
			X[beta].push_back(beta);
			beta = v[i];
		}
		else {
			if(!chk[t]) L.push_back(t);
			chk[t] = true;
			X[t].push_back(v[i]);
		}
	}
	cmpc = alpha;
	for(auto a : L) for(auto b : L) res[a][b] = 0;
	sort(L.begin(), L.end(), cmp);
	/*
	printf("alpha = %d, beta = %d, L = [", alpha, beta);
	for(auto a : L) printf("%d ", a);
	printf("]\n");
	*/
	if(L.empty()) brid(alpha, beta);
	else {
		brid(alpha, L[0]);
		for(int i = 0; i < L.size() - 1; i++) brid(L[i], L[i + 1]);
		brid(L.back(), beta);
	}
	for(auto a : L) f(X[a]);
}

void Solve(int N) {
	vector<int> v(N);
	for(int i = 0; i < N; i++) v[i] = i;
	f(v);
}

Compilation message

meetings.cpp: In function 'void f(std::vector<int>)':
meetings.cpp:55:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 2; i < v.size(); i++) {
                 ~~^~~~~~~~~~
meetings.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < L.size() - 1; i++) brid(L[i], L[i + 1]);
                  ~~^~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Wrong Answer [1]
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Wrong Answer [1]
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Wrong Answer [1]
7 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 864 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -