oj.uz

Submission #170653

# Submission time Handle Problem Language Result Execution time Memory
170653 2019-12-26T02:15:59 Z arnold518 Meetings (JOI19_meetings) C++14
0 / 100
 110 ms 568 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N;

mt19937 gen(time(NULL));

int rand(int l, int r)
{
	uniform_int_distribution<> dis(l, r);
	return dis(gen);
}

void answer(int a, int b)
{
	if(a>b) swap(a, b);
	Bridge(a, b);
}

void solve(vector<int> cand)
{
	if(cand.size()==1) return;
	int i, j;
	int u, v;

	u=rand(0, cand.size()-1);
	v=rand(0, cand.size()-1);
	while(u==v) v=rand(0, cand.size()-1);

	u=cand[u]; v=cand[v];

	map<int, vector<int>> M;
	vector<int> V;

	M[u].push_back(u);
	M[v].push_back(v);

	//for(auto it : cand) printf("%d ", it); printf(" : %d %d\n", u, v);

	for(auto now : cand)
	{
		if(now==u || now==v) continue;
		int t=Query(u, v, now);
		M[t].push_back(now);
		if(t!=u && t!=v) V.push_back(t);
	}

	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	stable_sort(V.begin(), V.end(), [&](const int &p, const int &q)
	{
		return Query(u, p, q)==q;
	});

	V.insert(V.begin(), u);
	V.push_back(v);

	for(i=1; i<V.size(); i++) answer(V[i], V[i-1]);

	for(auto it : M) solve(it.second);
}

void Solve(int _N)
{
	int i, j;
	N=_N;

	vector<int> V;
	for(i=0; i<N; i++) V.push_back(i);
	solve(V);
}

Compilation message

meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:63:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=1; i<V.size(); i++) answer(V[i], V[i-1]);
           ~^~~~~~~~~
meetings.cpp:28:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:70:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 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 248 KB Output is correct
5 Incorrect 2 ms 248 KB Wrong Answer [4]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 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 248 KB Output is correct
5 Incorrect 2 ms 248 KB Wrong Answer [4]
6 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 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 248 KB Output is correct
5 Incorrect 2 ms 248 KB Wrong Answer [4]
6 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 568 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -