Submission #131553

#	Time	Username	Problem	Language	Result	Execution time	Memory
131553		MrTEK	Meetings (JOI19_meetings)	C++14	29 / 100	3007 ms	3872 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef pair <int,int> ii;
 
const int N = 2e3 + 5;
 
vector <int> v;
int mark[N][N],d[N][N];
 
void bridge(int x,int y) {	
	Bridge(min(x,y),max(x,y));
}
 
void solve(vector <int> v) {
	if (v.size() < 2)
		return;
	if (v.size() == 2) {
		bridge(v[0],v[1]);
		return;
	}
	for (int i = 1 ; i < v.size() ; i++) {
		if (mark[v[0]][i])
			continue;
		vector <int> nv;
		nv.push_back(i);
		mark[v[0]][i] = 1;
		for (int j = i + 1 ; j < v.size() ; j++)
			if (mark[v[0]][j] == 0) {
				int temp = Query(v[0],v[i],v[j]);
				if (temp != v[0]) {
					mark[v[0]][j] = 1;
					nv.push_back(j);
					if (temp != v[i])
						d[v[0]][i] = 1;
					if (temp != v[j])
						d[v[0]][j] = 1;
				}
			}
		vector <int> nv2;
		for (auto i : nv)
			nv2.push_back(v[i]);
		for (int j = 0 ; j < nv.size() ; j++) {
			if (d[v[0]][nv[j]])
				continue;
			bool flag = true;
			for (int k = j + 1 ; k < nv.size() ; k++) {
				if (d[v[0]][nv[k]])
					continue;
				int temp = Query(v[0],v[nv[j]],v[nv[k]]);
				if (temp != v[nv[j]]) {
					flag = false;
					d[v[0]][nv[j]] = 1;
					break;
				}
				if (temp != v[nv[k]]) {
					d[v[0]][nv[k]] = 1;
				}
			}
			if (flag == true) {
				bridge(v[0],v[nv[j]]);
				break;
			}
		}
		solve(nv2);
	}
 
}
 
void Solve(int n) {
	for (int i = 0 ; i < n ; i++)
		v.push_back(i);
	solve(v);
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:26:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1 ; i < v.size() ; i++) {
                   ~~^~~~~~~~~~
meetings.cpp:32:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1 ; j < v.size() ; j++)
                        ~~^~~~~~~~~~
meetings.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0 ; j < nv.size() ; j++) {
                    ~~^~~~~~~~~~~
meetings.cpp:51:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = j + 1 ; k < nv.size() ; k++) {
                         ~~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 71