| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 403579 |
2021-05-13T09:44:13 Z |
errorgorn |
None (KOI18_family) |
C++17 |
|
29 ms |
58956 KB |
//雪花飄飄北風嘯嘯
//天地一片蒼茫
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
void rage(){
cout<<"NO"<<endl;
exit(0);
}
int n,m,k;
int root;
vector<int> al[300005];
int canon[300005]; //canonical index
int idx[300005]; //mapping back to normal index
ii span[300005]; //the span of canonical indexes
set<int> s[300005]; //the l endpoint of canonical index of children
int tkd[300005][20];
int IDX=0;
void dfs1(int i){
if (i<=k){
canon[i]=IDX;
idx[IDX]=i;
span[i]=ii(canon[i],canon[i]);
IDX++;
}
else{
span[i]=ii(1e9,-1e9);
for (auto &it:al[i]){
int curr=tkd[it][0]=i;
rep(x,0,20){
if (curr==-1) break;
curr=tkd[it][x+1]=tkd[curr][x];
}
dfs1(it);
span[i]=ii(
min(span[i].fi,span[it].fi),
max(span[i].se,span[it].se)
);
s[i].insert(span[it].fi);
}
s[i].insert(span[i].se+1);
}
}
set<ii> r[300005]; //ranges of the canonical indexes
ii span2[300005];
void dfs2(int i){
if (i<=k){
r[i].insert(ii(canon[i],canon[i]));
span2[i]=ii(canon[i],canon[i]);
}
else{
span2[i]=ii(1e9,-1e9);
for (auto &it:al[i]){
dfs2(it);
span2[i]=ii(
min(span2[i].fi,span2[it].fi),
max(span2[i].se,span2[it].se)
);
if (sz(r[it])>sz(r[i])) swap(r[it],r[i]);
for (auto it:r[it]){
auto temp=r[i].lb(it);
if (temp!=r[i].end() && (*temp).fi==it.se+1){
it.se=(*temp).se;
r[i].erase(temp);
}
temp=r[i].lb(it);
if (temp!=r[i].begin() && (*prev(temp)).se+1==it.fi){
it.fi=(*prev(temp)).fi;
r[i].erase(prev(temp));
}
r[i].insert(it);
}
}
}
//cout<<i<<" "<<span2[i].fi<<" "<<span2[i].se<<endl;
//for (auto &it:r[i]) cout<<it.fi<<" "<<it.se<<endl;
int curr=idx[span2[i].fi];
rep(x,20,0){
int temp=tkd[curr][x];
if (temp!=-1 && span2[i].fi<span[temp].fi && span[temp].se<span2[i].se){
curr=temp;
}
}
curr=tkd[curr][0];
//cout<<curr<<" "<<span2[curr].fi<<" "<<span2[curr].se<<endl;
//cout<<endl;
for (auto &it:r[i]){
if (!s[curr].count(it.fi)) rage();
if (!s[curr].count(it.se+1)) rage();
}
//cout<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n>>m>>k;
int t;
rep(x,1,n+1){
cin>>t;
if (t==0) root=x;
else al[t].pub(x);
}
memset(tkd,-1,sizeof(tkd));
dfs1(root);
//rep(x,1,n+1) cout<<span[x].fi<<" "<<span[x].se<<endl;
// rep(x,1,n+1){
// rep(y,0,2) cout<<tkd[x][y]<<" "; cout<<endl;
// }
rep(x,1,300005) al[x].clear();
rep(x,1,m+1){
cin>>t;
if (t==0) root=x;
else al[t].pub(x);
}
dfs2(root);
cout<<"YES"<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
58956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
58956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
58956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
58956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
