| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 430852 |
2021-06-17T07:06:32 Z |
8e7 |
Park (JOI17_park) |
C++14 |
|
329 ms |
636 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;
vector<int> adj[maxn], vert;
int ord[maxn];
bool found[maxn];
int qcnt = 0;
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> chain(vector<int> v) {
if (v.size() <= 3) return v;
int piv = v[1 + rand() % (v.size() - 2)];
vector<int> lef, rig;
lef.push_back(v[0]), rig.push_back(piv);
for (int i:v) que[i] = 1;
que[piv] = 0;
for (int i = 1;i < v.size() - 1;i++) {
if (v[i] != piv && query(v[0], v[i])) lef.push_back(v[i]);
else if (v[i] != piv) rig.push_back(v[i]);
}
lef.push_back(piv), rig.push_back(v.back());
lef = chain(lef), rig = chain(rig);
vector<int> ret = lef;
for (int i = 1;i < rig.size();i++) ret.push_back(rig[i]);
return ret;
}
int ti = 0;
void dfs(int n, int par) {
ord[ti++] = n;
for (int v:adj[n]) {
if (v != par) {
dfs(v, n);
}
}
}
int tot;
int search(int x) {
ti = 0;
dfs(vert[0], -1);
int low = 0, up = ti;
//pary(ord, ord + ti);
while (low + 1< up) {
int mid = (low + up) / 2;
for (int i = 0;i < ti;i++) que[ord[i]] = 1;
for (int i = mid;i < ti;i++) que[ord[i]] = 0;
if (query(x, vert[0])) up = mid;
else low = mid;
}
return ord[low];
}
void getpath(vector<int> cand, vector<int> & ret, int x, int y) {
if (cand.size() == 0) return;
for (int i:cand) que[i] = 0;
bool res = query(x, y);
for (int i:cand) que[i] = 1;
if (res) {
return;
} else {
if (cand.size() == 1) {
ret.push_back(cand[0]);
return;
} else {
vector<int> lef, rig;
for (int i = 0;i < cand.size();i++) {
if (i < cand.size() / 2) lef.push_back(cand[i]);
else rig.push_back(cand[i]);
}
getpath(lef, ret, x, y), getpath(rig, ret, x, y);
}
}
}
void Detect(int T, int N) {
tot = N;
if (T == 1) {
for (int i = 0;i < N;i++) {
for (int j = i + 1;j < N;j++) {
que[i] = 1, que[j] = 1;
if (query(i, j)) Answer(i, j);
que[i] = 0, que[j] = 0;
}
}
return;
}
srand(time(NULL));
for (int i = 0;i < N;i++) vert.push_back(i);
random_shuffle(vert.begin(), vert.end());
found[vert[0]] = 1;
for (int i = 1;i < N;i++) {
if (found[vert[i]]) continue;
for (int j = 0;j < N;j++) que[j] = 0;
que[vert[i]] = 1;
int anc = search(vert[i]);
for (int j = 0;j < N;j++) que[j] = 1;
vector<int> cand, path;
for (int j = 0;j < N;j++) {
if (!found[vert[j]] && j != i) cand.push_back(vert[j]);
}
path.push_back(vert[i]);
getpath(cand, path, vert[i], anc);
path.push_back(anc);
path = chain(path);
for (int j:path) found[j] = 1;
for (int j = 0;j < path.size() - 1;j++) {
ed.push_back({path[j], path[j + 1]});
adj[path[j]].push_back(path[j + 1]);
adj[path[j + 1]].push_back(path[j]);
}
}
/*
ti = 0;
dfs(vert[0], -1);
vector<int> rev;
for (int i = 0;i < N;i++) rev.push_back(ord[i]);
reverse(rev.begin(), rev.end());
for (int i = 0;i < N - 1;i++) {
vector<int> sub;
for (int j = i + 1;j < N;j++) {
sub.push_back(ord[j]);
}
solve(rev[i], sub);
}
*/
//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
park.cpp: In function 'std::vector<int> chain(std::vector<int>)':
park.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i = 1;i < v.size() - 1;i++) {
| ~~^~~~~~~~~~~~~~
park.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 1;i < rig.size();i++) ret.push_back(rig[i]);
| ~~^~~~~~~~~~~~
park.cpp: In function 'void getpath(std::vector<int>, std::vector<int>&, int, int)':
park.cpp:95:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int i = 0;i < cand.size();i++) {
| ~~^~~~~~~~~~~~~
park.cpp:96:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | if (i < cand.size() / 2) lef.push_back(cand[i]);
| ~~^~~~~~~~~~~~~~~~~
park.cpp: In function 'void Detect(int, int)':
park.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for (int j = 0;j < path.size() - 1;j++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
5 ms |
332 KB |
Output is correct |
| 3 |
Correct |
5 ms |
360 KB |
Output is correct |
| 4 |
Correct |
5 ms |
332 KB |
Output is correct |
| 5 |
Correct |
5 ms |
356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
140 ms |
524 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
240 ms |
636 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
452 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
329 ms |
480 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
