| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 521422 |
2022-02-02T06:03:09 Z |
azberjibiou |
Park (JOI17_park) |
C++17 |
|
229 ms |
900 KB |
#include "park.h"
#include <bits/stdc++.h>
using namespace std;
int N;
static int Place[1400];
bool Chk[1400];
int now;
vector <int> new_check;
vector <int> to_check;
vector <int> v[1400];
void solv(int s, int e)
{
for(int i=s;i<=e;i++) Place[to_check[i]]=0;
int val=Ask(0, now, Place);
if(val==1) return;
for(int i=s;i<=e;i++) Place[to_check[i]]=1;
if(s==e)
{
new_check.push_back(to_check[s]);
return;
}
int mid=(s+e)/2;
solv(s, mid);
solv(mid+1, e);
}
bool cmp1(int a, int b)
{
Place[a]=0;
int val=Ask(0, b, Place);
Place[a]=1;
return val==0;
}
vector <int> tree[1400];
vector <int> euler;
void dfs(int now, int pre)
{
euler.push_back(now);
for(int nxt : tree[now]) if(nxt!=pre)
{
dfs(nxt, now);
euler.push_back(now);
}
}
int cnt;
int solv_par(int now, int pre)
{
cnt++;
int tcnt=0;
for(int i=0;i<N;i++) tcnt+=tree[i].size();
assert(tcnt==2*cnt-2);
euler.clear();
dfs(0, -1);
//assert(euler.size()==2*cnt-1);
for(int i=0;i<N;i++) Place[i]=0;
Place[now]=1;
set <int> s;
s.insert(euler.size());
vector <int> adj;
if(pre!=-1)
{
adj.push_back(pre);
for(int i=0;i<euler.size();i++) if(euler[i]==pre) s.insert(i);
}
int cur=0;
while(!s.empty())
{
int nxt=*s.begin();
s.erase(s.begin());
if(cur==nxt)
{
cur++;
continue;
}
for(int i=cur;i<=nxt-1;i++) Place[euler[i]]=1;
int check_val=Ask(min(now, euler[cur]), max(now, euler[cur]), Place);
for(int i=cur;i<=nxt-1;i++) Place[euler[i]]=0;
if(check_val==0)
{
cur=nxt+1;
continue;
}
s.insert(nxt);
int l=cur, r=nxt-1;
assert(l<=r);
while(l!=r)
{
int mid=(l+r)/2;
for(int i=l;i<=mid;i++) Place[euler[i]]=1;
int val=Ask(min(now, euler[l]), max(now, euler[l]), Place);
for(int i=l;i<=mid;i++) Place[euler[i]]=0;
if(val==1) r=mid;
else l=mid+1;
}
for(int i=0;i<euler.size();i++) if(euler[i]==euler[l]) s.insert(i);
adj.push_back(euler[l]);
cur=l;
}
assert(!adj.empty());
tree[now].push_back(adj[0]);
tree[adj[0]].push_back(now);
for(int ele : adj)
{
v[ele].push_back(now);
v[now].push_back(ele);
}
}
void Detect(int T, int n) {
N=n;
Chk[0]=true;
for(int i=1;i<N;i++) to_check.push_back(i);
while(!to_check.empty())
{
for(int i=0;i<N;i++) Place[i]=1;
now=to_check.back();
to_check.pop_back();
new_check.push_back(now);
if(!to_check.empty()) solv(0, to_check.size()-1);
sort(new_check.begin(), new_check.end(), cmp1);
solv_par(new_check[0], -1);
for(int i=1;i<new_check.size();i++)
{
solv_par(new_check[i], new_check[i-1]);
}
for(int ele : new_check) Chk[ele]=true;
new_check.clear();
to_check.clear();
for(int i=0;i<N;i++) if(!Chk[i]) to_check.push_back(i);
}
/*for(int i=0;i<N;i++)
{
printf("%d: ", i);
for(int ele : v[i]) printf("%d ", ele);
printf("\n");
}*/
for(int i=0;i<N;i++)
{
for(int ele : v[i]) if(ele<i) Answer(ele, i);
}
}
Compilation message
park.cpp: In function 'int solv_par(int, int)':
park.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0;i<euler.size();i++) if(euler[i]==pre) s.insert(i);
| ~^~~~~~~~~~~~~
park.cpp:95:22: 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<euler.size();i++) if(euler[i]==euler[l]) s.insert(i);
| ~^~~~~~~~~~~~~
park.cpp: In function 'void Detect(int, int)':
park.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i=1;i<new_check.size();i++)
| ~^~~~~~~~~~~~~~~~~
park.cpp: In function 'int solv_par(int, int)':
park.cpp:57:15: warning: control reaches end of non-void function [-Wreturn-type]
57 | set <int> s;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
229 ms |
900 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
716 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
716 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
716 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
