Can someone help me understand why this code works for g++ 17 but not on g++ 20?↵
~~~~~↵
//......↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
#define ra(a) a.begin(),a.end()↵
#define endl "\n"↵
#define pb push_back↵
#define no cout<<"No"<<endl↵
#define No cout<<"NO"<<endl↵
#define yes cout<<"Yes"<<endl↵
#define Yes cout<<"YES"<<endl↵
#define mod 1000000007↵
#define inf LLONG_MAX↵
#define what_is(x) cout<<#x<<": "<<x<<endl;↵
↵
vector<int>lvl;↵
map<int,int>val;↵
↵
bool cmp(int a, int b)↵
{↵
return lvl[a]>lvl[b];↵
}↵
↵
int dfs(vector<int>T[], int v, int p)↵
{↵
for(int c:T[v]){↵
if(c==p) continue;↵
dfs(T, c, v);↵
lvl[v] = max(lvl[v], lvl[c]);↵
}↵
sort(ra(T[v]), cmp);↵
lvl[v]++;↵
}↵
↵
void allot(vector<int>T[], int v, int p, int& cur)↵
{↵
if(v&&T[v].size()==1){↵
val[v] = cur++;↵
}↵
for(int c:T[v]){↵
if(c==p) continue;↵
allot(T, c, v, cur);↵
}↵
}↵
↵
int visit_tree(vector<int>T[], vector<int>& seq, int v, int p)↵
{↵
int mn = inf;↵
// what_is(v);↵
// what_is(val[v]);↵
if(val[v]) mn = val[v];↵
for(int c:T[v]){↵
if(c==p) continue;↵
mn = min(mn, visit_tree(T, seq, c, v));↵
}↵
seq.pb(mn);↵
return mn;↵
}↵
↵
int lis(vector<int> const& a) {↵
int n = a.size();↵
const int INF = 1e9;↵
vector<int> d(n+1, INF);↵
d[0] = -INF;↵
↵
for (int i = 0; i < n; i++) {↵
int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();↵
if (d[l-1] <= a[i] && a[i] < d[l])↵
d[l] = a[i];↵
}↵
↵
int ans = 0;↵
for (int l = 0; l <= n; l++) {↵
if (d[l] < INF)↵
ans = l;↵
}↵
return ans;↵
}↵
↵
void solve()↵
{↵
int n;cin>>n;↵
vector<int>T[n];↵
for(int i=1;i<n;i++){↵
int x;cin>>x;↵
x--;↵
T[i].pb(x);↵
T[x].pb(i);↵
}↵
↵
lvl.resize(n,0);↵
dfs(T, 0, -1);↵
↵
val.clear();↵
int cur = 1;↵
allot(T, 0, -1, cur);↵
↵
vector<int>seq;↵
visit_tree(T, seq, 0, -1);↵
↵
// for(int x:seq) cout<<x<<" "; cout<<endl;↵
cout<<lis(seq)<<endl;↵
}↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(0);cin.tie(0);↵
int t=1;↵
// cin>>t;↵
for(int i=0;i<t;i++){↵
// cout<<"Case #"<<i+1<<": \n";↵
solve();↵
}↵
}↵
/*↵
↵
*/↵
~~~~~↵
[submission:240675477]↵
↵
//......↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define int long long↵
#define ra(a) a.begin(),a.end()↵
#define endl "\n"↵
#define pb push_back↵
#define no cout<<"No"<<endl↵
#define No cout<<"NO"<<endl↵
#define yes cout<<"Yes"<<endl↵
#define Yes cout<<"YES"<<endl↵
#define mod 1000000007↵
#define inf LLONG_MAX↵
#define what_is(x) cout<<#x<<": "<<x<<endl;↵
↵
vector<int>lvl;↵
map<int,int>val;↵
↵
bool cmp(int a, int b)↵
{↵
return lvl[a]>lvl[b];↵
}↵
↵
int dfs(vector<int>T[], int v, int p)↵
{↵
for(int c:T[v]){↵
if(c==p) continue;↵
dfs(T, c, v);↵
lvl[v] = max(lvl[v], lvl[c]);↵
}↵
sort(ra(T[v]), cmp);↵
lvl[v]++;↵
}↵
↵
void allot(vector<int>T[], int v, int p, int& cur)↵
{↵
if(v&&T[v].size()==1){↵
val[v] = cur++;↵
}↵
for(int c:T[v]){↵
if(c==p) continue;↵
allot(T, c, v, cur);↵
}↵
}↵
↵
int visit_tree(vector<int>T[], vector<int>& seq, int v, int p)↵
{↵
int mn = inf;↵
// what_is(v);↵
// what_is(val[v]);↵
if(val[v]) mn = val[v];↵
for(int c:T[v]){↵
if(c==p) continue;↵
mn = min(mn, visit_tree(T, seq, c, v));↵
}↵
seq.pb(mn);↵
return mn;↵
}↵
↵
int lis(vector<int> const& a) {↵
int n = a.size();↵
const int INF = 1e9;↵
vector<int> d(n+1, INF);↵
d[0] = -INF;↵
↵
for (int i = 0; i < n; i++) {↵
int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();↵
if (d[l-1] <= a[i] && a[i] < d[l])↵
d[l] = a[i];↵
}↵
↵
int ans = 0;↵
for (int l = 0; l <= n; l++) {↵
if (d[l] < INF)↵
ans = l;↵
}↵
return ans;↵
}↵
↵
void solve()↵
{↵
int n;cin>>n;↵
vector<int>T[n];↵
for(int i=1;i<n;i++){↵
int x;cin>>x;↵
x--;↵
T[i].pb(x);↵
T[x].pb(i);↵
}↵
↵
lvl.resize(n,0);↵
dfs(T, 0, -1);↵
↵
val.clear();↵
int cur = 1;↵
allot(T, 0, -1, cur);↵
↵
vector<int>seq;↵
visit_tree(T, seq, 0, -1);↵
↵
// for(int x:seq) cout<<x<<" "; cout<<endl;↵
cout<<lis(seq)<<endl;↵
}↵
↵
signed main()↵
{↵
ios_base::sync_with_stdio(0);cin.tie(0);↵
int t=1;↵
// cin>>t;↵
for(int i=0;i<t;i++){↵
// cout<<"Case #"<<i+1<<": \n";↵
solve();↵
}↵
}↵
/*↵
↵
*/↵
~~~~~
[submission:240675477]↵
↵
