| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 429739 |
2021-06-16T09:01:27 Z |
8e7 |
Park (JOI17_park) |
C++14 |
|
1390 ms |
696 KB |
#include "park.h"
//Challenge: Accepted
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <random>
#include <time.h>
#include <assert.h>
#include <unordered_map>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
template <class T> void pary(T l, T r) {
while (l != r) {cout << *l << " ";l++;}
cout << endl;
}
#define ll long long
#define ld long double
#define maxn 1405
#define mod 1000000007
#define pii pair<long long, long long>
#define ff first
#define ss second
static int que[maxn];
vector<pii> ed;
int qcnt = 0;
void group(vector<int> root, vector<int> nom, int cent);
int query(int a, int b) {
if (a > b) swap(a, b);
if (a == b || (que[a] == 0) || (que[b] == 0)) return 0;
qcnt++;
return Ask(a, b, que);
}
vector<int> roots;
vector<vector<int> > subs;
void solve(vector<int> v) {
roots.clear(), subs.clear();
//pary(v.begin(), v.end());
if (v.size() < 2) return;
if (v.size() == 2) {
ed.push_back({v[0], v[1]});
return;
}
//debug(v.size());
random_shuffle(v.begin(), v.end());
int cent = v[0];
for (int i = 0;i < maxn;i++) que[i] = 0;
for (int i:v) que[i] = 1;
if (v.size() > 5) {
int num = __lg(v.size()), ma = 0, best = 0, f = 0;
for (int i:v) {
que[i] = 0;
int cnt = 0;
for (int j = 0;j < num;j++) {
int ix = rand() % v.size(), iy = rand() % v.size();
if (v[ix] == i) ix = (ix + 1) % v.size();
while (iy == ix || v[iy] == i) {
iy = (iy + 1) % v.size();
}
cnt += query(v[ix], v[iy]) ? 0 : 1;
}
que[i] = 1;
if (cnt > ma) {
ma = cnt, best = i;
}
if (cnt >= (num / 2)) {
cent = i, f = 1;
break;
}
}
if (!f) cent = best;
}
//debug(cent);
for (int i:v) que[i] = 0;
que[cent] = 1;
vector<int> adj, sub;
for (int i:v) {
if (i == cent) continue;
que[i] = 1;
if (query(i, cent)) {
ed.push_back({i, cent}), adj.push_back(i);
} else {
sub.push_back(i);
}
que[i] = 0;
}
for (int i:v) que[i] = 1;
group(adj, sub, cent);
for (int i:v) que[i] = 0;
vector<vector<int> > rec;
for (auto i:subs) rec.push_back(i);
int siz = 0;
for (auto i:rec) {
siz += i.size();
solve(i);
}
assert(siz == v.size() - 1);
}
void group(vector<int> root, vector<int> nom, int cent) {
if (root.size() == 0) return;
if (root.size() == 1) {
nom.push_back(root[0]);
subs.push_back(nom);
return;
}
vector<int> ar, br, an, bn;
for (int i = 0;i < root.size();i++) {
if (i < (root.size() / 2)) ar.push_back(root[i]);
else br.push_back(root[i]);
}
for (int i:ar) que[i] = 0;
for (int i:nom) {
if (!query(i, cent)) {
an.push_back(i);
} else {
bn.push_back(i);
}
}
for (int i:ar) que[i] = 1;
group(ar, an, cent), group(br, bn, cent);
}
void Detect(int T, int N) {
srand(time(NULL));
vector<int> ini;
for (int i = 0;i < N;i++) ini.push_back(i);
solve(ini);
//debug(qcnt);
//assert(ed.size() == N - 1);
for (auto i:ed) {
if (i.ff > i.ss) swap(i.ff, i.ss);
Answer(i.ff, i.ss);
}
}
/*
4
10 9
0 1
0 2
1 3
2 4
1 5
2 6
2 7
7 8
5 9
4
8 7
0 1
0 2
0 3
0 4
0 5
0 6
0 7
*/
Compilation message
In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
from park.cpp:11:
park.cpp: In function 'void solve(std::vector<int>)':
park.cpp:105:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | assert(siz == v.size() - 1);
| ~~~~^~~~~~~~~~~~~~~
park.cpp: In function 'void group(std::vector<int>, std::vector<int>, int)':
park.cpp:115:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (int i = 0;i < root.size();i++) {
| ~~^~~~~~~~~~~~~
park.cpp:116:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | if (i < (root.size() / 2)) ar.push_back(root[i]);
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Wrong Answer[6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
456 KB |
Output is correct |
| 2 |
Correct |
53 ms |
500 KB |
Output is correct |
| 3 |
Correct |
49 ms |
528 KB |
Output is correct |
| 4 |
Correct |
72 ms |
524 KB |
Output is correct |
| 5 |
Correct |
75 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
152 ms |
692 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
696 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1390 ms |
396 KB |
Wrong Answer[5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
