| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 572013 |
2022-06-03T09:20:18 Z |
cadmiumsky |
Park (JOI17_park) |
C++14 |
|
4 ms |
3796 KB |
#include "park.h"
#include <bits/stdc++.h>
using namespace std;
using vectorit = vector<int>::iterator;
using pii = pair<int,int>;
const int nmax = 14e2 + 5;
int n;
int lg[nmax];
namespace Query {
int Place[nmax];
bool query(int s, int t, vectorit l, vectorit r) {
for(int i = 0; i < n; i++)
Place[i] = 0;
while(l != r)
Place[*l] = 1,
l++;
Place[s] = 1;
Place[t] = 1;
if(s > t)
swap(s, t);
return Ask(s, t, Place);
}
bool query(int s, int t, vector<int> v) {
return query(s, t, v.begin(), v.end());
}
};
using namespace Query;
class Tree {
vector< vector<int> > t;
public:
int root;
vector<int> preord;
vector<pii> edg;
unordered_set<int> V;
void addedge(int x, int y) {
V.insert(x), V.insert(y);
t[x].push_back(y), t[y].push_back(x);
}
void dfspreord(int node, int f) {
preord.push_back(node);
for(auto x : t[node]) {
if(x == f)
continue;
dfspreord(x, node);
}
return;
}
void dfspreord() {preord.clear(); dfspreord(root, root); }
vector<Tree> decompound(int elim) {
vector<Tree> rez;
function<void(int,int)> push = [&](int node, int f) {
if(node != f)
rez.back().addedge(node, f);
for(auto x : t[node])
if(x != f && x != elim)
push(x, node);
return;
};
for(auto x : t[elim]) {
rez.push_back(Tree(t.size(), x));
push(x, x);
rez.back().dfspreord();
}
return rez;
}
int binsearch(int aux) {
if(query(aux, preord[0], preord.begin(), preord.begin()))
return preord[0];
int lim = 0, temp;
for(int i = lg[preord.size()]; i >= 0; i--) {
temp = min((int)preord.size(), lim + (1 << i));
if(!query(aux, preord[0], preord.begin(), preord.begin() + temp))
lim = temp;
}
assert(lim < preord.size());
return preord[lim];
}
~Tree() {
preord.clear();
t.clear();
}
Tree(int len = n, int rt = 0) {
t.clear();
preord.clear();
t.resize(len);
V.insert(rt);
root = rt;
}
};
vector<pii> edg;
vector<Tree> trees;
void add(int node) {
vector<int> pivots, cpy;
vector<Tree> st;
for(int i = 0; i < trees.size(); i++) { // identifying newly connected components
Tree& t = trees[i];
if(query(node, t.root, t.preord))
st.push_back(t),
swap(trees.back(), t),
pivots.push_back(t.binsearch(node)),
trees.pop_back();
}
if(st.empty()) { // if there are none, continue
trees.push_back(Tree(n, node));
trees.back().dfspreord();
return;
}
for(auto a : pivots)
edg.emplace_back(a, node);
cpy = pivots;
st[0].addedge(pivots[0], node);
while(st.size() > 1) { // merging all components tied to node
auto& t = st.back();
for(auto [a, b] : t.edg)
st[0].addedge(a, b);
st[0].addedge(node, pivots.back());
st.pop_back();
pivots.pop_back();
}
st.back().dfspreord();
trees.push_back(st[0]); // adding it to the legitimate list
pivots = move(cpy);
auto tempst = st[0].decompound(node);
st.clear();
for(auto t : tempst) { // continuing the reduction
int val = -1;
for(int i = 0; i < pivots.size(); i++)
if(t.V.count(pivots[i])) {
val = pivots[i];
swap(pivots.back(), pivots[i]);
pivots.pop_back();
break;
}
assert(val != -1);
auto tempt = t.decompound(val);
copy(tempt.begin(), tempt.end(), back_inserter(st));
tempt.clear();
}
tempst.clear();
while(!st.empty()) { // finding all edges within forest
if(!query(node, st.back().root, st.back().preord)) {
st.pop_back();
continue;
}
int aux = st.back().binsearch(node);
edg.emplace_back(aux, node);
auto t = st.back();
st.pop_back();
auto vt = t.decompound(aux);
copy(vt.begin(), vt.end(), back_inserter(st));
vt.clear();
}
}
void Detect(int T, int N) {
n = N;
lg[1] = 0;
for(int i = 2; i <= n; i++)
lg[i] = lg[i >> 1] + 1;
for(int i = 0; i < n; i++)
add(i);
for(auto [a, b] : edg) {
if(a > b)
swap(a, b);
//cerr << a << ' ' << b << '\n';
Answer(a, b);
}
return;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from park.cpp:2:
park.cpp: In member function 'int Tree::binsearch(int)':
park.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | assert(lim < preord.size());
| ~~~~^~~~~~~~~~~~~~~
park.cpp: In function 'void add(int)':
park.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i = 0; i < trees.size(); i++) { // identifying newly connected components
| ~~^~~~~~~~~~~~~~
park.cpp:120:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
120 | for(auto [a, b] : t.edg)
| ^
park.cpp:135:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for(int i = 0; i < pivots.size(); i++)
| ~~^~~~~~~~~~~~~~~
park.cpp: In function 'void Detect(int, int)':
park.cpp:171:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
171 | for(auto [a, b] : edg) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
2968 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
2900 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
3796 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
2884 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
