oj.uz

Submission #123702

# Submission time Handle Problem Language Result Execution time Memory
123702 2019-07-02T04:57:57 Z 이온조(#3029) Meetings (JOI19_meetings) C++14
0 / 100
 96 ms 16296 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using tiii = tuple<int, int, int>;

int query(int u, int v, int w) {
	if(u == v) return u;
	if(v == w) return v;
	if(w == u) return w;
	return Query(u, v, w);
}

void bridge(int u, int v) {
	// printf("%d <---> %d\n", u, v);
	Bridge(u, v);
}

int D[2009][2009];

void go(vector<int> &S, int u) {
	int N = S.size();
	if(N == 1) return;
	if(N == 2) {
		bridge(S[0], S[1]);
		return;
	}
	int v = S[rand() % N];

	vector<bool> chk(N, 0);
	map<int, vector<int> > mp;
	vector<int> T, U, V;
	for(auto& it: S) {
		int Q = query(u, v, it);
		mp[Q].push_back(it);
		if(Q != u && Q != v) T.push_back(Q);
	}
	for(auto& it: mp) go(it.second, it.first);

	if(T.size()) {
		sort(T.begin(), T.end(), [&](int X, int Y) {
			if(D[X][Y] != -1) return D[X][Y];
			int f = (query(u, X, Y) == X);
			D[X][Y] = f; D[Y][X] = !f;
			return f;
		});
		T.resize(unique(T.begin(), T.end()) - T.begin());
		for(int i=1; i<T.size(); i++) bridge(T[i-1], T[i]);
		bridge(u, T[0]); bridge(T.back(), v);
	}
	else bridge(u, v);
}

void Solve(int N) {
	srand(190702);
	vector<int> S;
	for(int i=0; i<N; i++) S.push_back(i);
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			if(i == j) D[i][j] = 0;
			else D[i][j] = -1;
		}
	}
	go(S, 0);
}

Compilation message

meetings.cpp: In function 'void go(std::vector<int>&, int)':
meetings.cpp:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1; i<T.size(); i++) bridge(T[i-1], T[i]);
                ~^~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 16296 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -