Submission #994988

#TimeUsernameProblemLanguageResultExecution timeMemory
994988edogawa_somethingConstruction of Highway (JOI18_construction)C++17
16 / 100
2043 ms45896 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vii; typedef pair<ll,ll> pii; #define F first #define S second #define all(v) v.begin(),v.end() #define pb push_back #define pow poww const int M=1e6+10; const ll mod=998244353; const ll inf=2e18; ll pow(ll x,ll y){ ll res=1; x%=mod; while(y>0){ if(y%2==1){ res*=x,res%=mod; } x*=x,x%=mod; y/=2; } return res; } ll n,C[M],a[M],pa[M],b[M]; vii adj[M]; map<ll,ll>mp; void update(ll x){ for(int i=x;i<=n;i+=(i&-i)) b[i]++; } ll query(ll x){ ll res=0; for(int i=x;i>0;i-=(i&-i)) res+=b[i]; return res; } ll calc(ll x){ vii v; while(x!=1) v.pb(a[x]),x=pa[x]; v.pb(a[1]); for(int i=0;i<=2*n;i++) b[i]=0; ll ans=0; for(auto it:v) update(it),ans+=query(it-1); return ans; } void change(ll x){ ll z=a[x]; while(x!=1) a[x]=z,x=pa[x]; a[1]=z; } int main(){ ios_base::sync_with_stdio(0),cin.tie(0); ll TC=1; //cin>>TC; while(TC--){ cin>>n; for(int i=0;i<n;i++) cin>>C[i],mp[C[i]]=1; ll cnt=1; for(auto &it:mp) it.S=cnt++; for(int i=0;i<n;i++){ a[i+1]=mp[C[i]]; } for(int i=0;i<n-1;i++){ ll x,y; cin>>x>>y; pa[y]=x; cout<<calc(x)<<'\n'; change(y); } } return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...