| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 428713 |
2021-06-15T14:01:40 Z |
tqbfjotld |
Park (JOI17_park) |
C++14 |
|
114 ms |
608 KB |
#include "park.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> curknown;
set<int> adjl[2005];
int dep[2005];
int n;
int querything[1405];
void dfs(int node, int pa){
for (auto x : adjl[node]){
if (x==pa) continue;
dep[x] = dep[node]+1;
dfs(x,node);
}
}
int query(int a, int b, vector<int> stuff){
memset(querything,0,sizeof(querything));
for (int x = 0; x<n; x++) querything[x] = 0;
for (int x : stuff){
querything[x] = 1;
}
querything[a] = 1;
querything[b] = 1;
return Ask(a,b,querything);
}
int not_query(int a, int b, vector<int> stuff){
memset(querything,0,sizeof(querything));
for (int x = 0; x<n; x++) querything[x] = 1;
for (int x : stuff){
querything[x] = 0;
}
querything[a] = 1;
querything[b] = 1;
return Ask(a,b,querything);
}
/*
1 6 5
0 3
0 1
1 4
1 2
2 5
*/
void find_lowest(int node){
// printf("hi %d\n",node);
int l = 0;
int r = -1;
for (int x = 0; x<n; x++){
r = max(r,dep[x]);
}
while (l+1<r){
// printf("l = %d, r = %d\n",l,r);
int mid = (l+r)/2;
vector<int> stuff;
for (int x = 1; x<n; x++){
if (dep[x]!=0 && dep[x]<=mid){
stuff.push_back(x);
// printf("stuff %d\n",x);
}
}
int res = query(0,node,stuff);
if (res==1){
r = mid;
}
else l = mid;
}
l=r;
//printf("l = %d\n",l);
vector<int> nodes;
for (int x = 0; x<n; x++){
if (dep[x]==l) {nodes.push_back(x);
// printf("%d added \n",x);
}
}
while (nodes.size()>1){
vector<int> t;
for (int x = 0; x<nodes.size()/2; x++){
t.push_back(nodes[x]);
}
for (int x = 0; x<n; x++){
// if (dep[x]!=0 && dep[x]<l) t.push_back(x);
}
if (!not_query(0,node,nodes)){
nodes = t;
}
else{
vector<int> t2;
for (int x = nodes.size()/2; x<nodes.size(); x++){
t2.push_back(x);
}
nodes = t2;
}
}
int pnode = nodes[0];
// printf("pnode = %d\n",pnode);
for (auto x : adjl[pnode]){
if (dep[x]<dep[pnode]) continue;
if (!not_query(pnode,x,{node})){
int num = x;
adjl[pnode].erase(adjl[pnode].lower_bound(num));
adjl[num].erase(adjl[num].lower_bound(pnode));
adjl[pnode].insert(node);
adjl[num].insert(node);
adjl[node].insert(num);
adjl[node].insert(pnode);
// printf("insert %d between %d and %d\n",node,num,pnode);
return;
}
}
//printf("insert %d after %d\n",node,pnode);
adjl[pnode].insert(node);
adjl[node].insert(pnode);
}
void Detect(int T, int N) {
curknown.push_back(1);
adjl[0].insert(1);
adjl[1].insert(0);
dep[0] = 1;
n = N;
for (int x = 2; x<N; x++){
dfs(0,-1);
if (not_query(0,x,curknown)){
//printf("hi %d\n",x);
adjl[0].insert(x);
adjl[x].insert(0);
}
else{
find_lowest(x);
}
}
for (int x = 0; x<N; x++){
for (auto y : adjl[x]){
if (x<y){
Answer(x,y);
}
}
}
}
Compilation message
park.cpp: In function 'void find_lowest(int)':
park.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int x = 0; x<nodes.size()/2; x++){
| ~^~~~~~~~~~~~~~~
park.cpp:92:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int x = nodes.size()/2; x<nodes.size(); x++){
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
592 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
608 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
540 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
532 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
