답안 #1092675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1092675	2024-09-24T18:00:26 Z	Trisanu_Das	Cat Exercise (JOI23_ho_t4)	C++17	컴파일 오류	0 ms	0 KB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n;
int a[N], pa[N], sz[N], hv[N], lv[N], hd[N], ord[N], fa[N];
vector<int> adj[N];
long long dp[N];
 
void dfs(int u,int p = 0){
    pa[u] = p;
    sz[u] = 1;
    lv[u] = lv[p] + 1;
    for(auto v : adj[u]) 
        if(v != p){
            dfs(v,u);
            sz[u]+=sz[v];
            if(sz[v]>sz[hv[u]])hv[u]=v;
        }
}
 
void hld(int u,int p=0){
    if(!hd[u])hd[u]=u;
    if(hv[u])hd[hv[u]]=hd[u],hld(hv[u],u);
    for(auto v:adj[u])if(v!=p&&v!=hv[u])hld(v,u);
}
 
int lca(int u,int v){
    while(hd[u]!=hd[v]){
        if(lv[hd[u]]<lv[hd[v]])swap(u,v);
        u=pa[hd[u]];
    }
    return lv[u]<lv[v]?u:v;
}
 
int dist(int u,int v){
    return lv[u]+lv[v]-2*lv[lca(u,v)];
}
 
int fp(int u){
    return fa[u]=fa[u]==u?u:fp(fa[u]);
}
 
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++)cin >> a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    dfs(1);
    hld(1);
    iota(fa+1,fa+n+1,1);
    iota(ord+1,ord+n+1,1);
    sort(ord+1,ord+n+1,[&](int i,int j){
        return a[i]<a[j];
    });
    for(int i=1;i<=n;i++){
        int u=ord[i];
        for(auto v:adj[u])if(a[u]>a[v]){
            v=fp(v);
            dp[u]=max(dp[u],dp[v]+dist(u,v));
            fa[v]=u;
        }
    }
    cout << dp[ord[n]];
}

Compilation message

Main.cpp:6:7: error: 'N' was not declared in this scope
    6 | int a[N], pa[N], sz[N], hv[N], lv[N], hd[N], ord[N], fa[N];
      |       ^
Main.cpp:6:14: error: 'N' was not declared in this scope
    6 | int a[N], pa[N], sz[N], hv[N], lv[N], hd[N], ord[N], fa[N];
      |              ^
Main.cpp:6:21: error: 'N' was not declared in this scope
    6 | int a[N], pa[N], sz[N], hv[N], lv[N], hd[N], ord[N], fa[N];
      |                     ^
Main.cpp:6:28: error: 'N' was not declared in this scope
    6 | int a[N], pa[N], sz[N], hv[N], lv[N], hd[N], ord[N], fa[N];
      |                            ^
Main.cpp:6:35: error: 'N' was not declared in this scope
    6 | int a[N], pa[N], sz[N], hv[N], lv[N], hd[N], ord[N], fa[N];
      |                                   ^
Main.cpp:6:42: error: 'N' was not declared in this scope
    6 | int a[N], pa[N], sz[N], hv[N], lv[N], hd[N], ord[N], fa[N];
      |                                          ^
Main.cpp:6:50: error: 'N' was not declared in this scope
    6 | int a[N], pa[N], sz[N], hv[N], lv[N], hd[N], ord[N], fa[N];
      |                                                  ^
Main.cpp:6:57: error: 'N' was not declared in this scope
    6 | int a[N], pa[N], sz[N], hv[N], lv[N], hd[N], ord[N], fa[N];
      |                                                         ^
Main.cpp:7:17: error: 'N' was not declared in this scope
    7 | vector<int> adj[N];
      |                 ^
Main.cpp:8:14: error: 'N' was not declared in this scope
    8 | long long dp[N];
      |              ^
Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:11:5: error: 'pa' was not declared in this scope; did you mean 'p'?
   11 |     pa[u] = p;
      |     ^~
      |     p
Main.cpp:12:5: error: 'sz' was not declared in this scope
   12 |     sz[u] = 1;
      |     ^~
Main.cpp:13:5: error: 'lv' was not declared in this scope
   13 |     lv[u] = lv[p] + 1;
      |     ^~
Main.cpp:14:18: error: 'adj' was not declared in this scope
   14 |     for(auto v : adj[u])
      |                  ^~~
Main.cpp:18:25: error: 'hv' was not declared in this scope
   18 |             if(sz[v]>sz[hv[u]])hv[u]=v;
      |                         ^~
Main.cpp: In function 'void hld(long long int, long long int)':
Main.cpp:23:9: error: 'hd' was not declared in this scope; did you mean 'hld'?
   23 |     if(!hd[u])hd[u]=u;
      |         ^~
      |         hld
Main.cpp:24:8: error: 'hv' was not declared in this scope
   24 |     if(hv[u])hd[hv[u]]=hd[u],hld(hv[u],u);
      |        ^~
Main.cpp:24:14: error: 'hd' was not declared in this scope; did you mean 'hld'?
   24 |     if(hv[u])hd[hv[u]]=hd[u],hld(hv[u],u);
      |              ^~
      |              hld
Main.cpp:25:16: error: 'adj' was not declared in this scope
   25 |     for(auto v:adj[u])if(v!=p&&v!=hv[u])hld(v,u);
      |                ^~~
Main.cpp:25:35: error: 'hv' was not declared in this scope
   25 |     for(auto v:adj[u])if(v!=p&&v!=hv[u])hld(v,u);
      |                                   ^~
Main.cpp: In function 'long long int lca(long long int, long long int)':
Main.cpp:29:11: error: 'hd' was not declared in this scope; did you mean 'hld'?
   29 |     while(hd[u]!=hd[v]){
      |           ^~
      |           hld
Main.cpp:30:12: error: 'lv' was not declared in this scope; did you mean 'v'?
   30 |         if(lv[hd[u]]<lv[hd[v]])swap(u,v);
      |            ^~
      |            v
Main.cpp:31:11: error: 'pa' was not declared in this scope
   31 |         u=pa[hd[u]];
      |           ^~
Main.cpp:33:12: error: 'lv' was not declared in this scope; did you mean 'v'?
   33 |     return lv[u]<lv[v]?u:v;
      |            ^~
      |            v
Main.cpp: In function 'long long int dist(long long int, long long int)':
Main.cpp:37:12: error: 'lv' was not declared in this scope; did you mean 'v'?
   37 |     return lv[u]+lv[v]-2*lv[lca(u,v)];
      |            ^~
      |            v
Main.cpp: In function 'long long int fp(long long int)':
Main.cpp:41:12: error: 'fa' was not declared in this scope; did you mean 'fp'?
   41 |     return fa[u]=fa[u]==u?u:fp(fa[u]);
      |            ^~
      |            fp
Main.cpp: In function 'int main()':
Main.cpp:47:33: error: 'a' was not declared in this scope
   47 |     for(int i=1;i<=n;i++)cin >> a[i];
      |                                 ^
Main.cpp:51:9: error: 'adj' was not declared in this scope
   51 |         adj[u].emplace_back(v);
      |         ^~~
Main.cpp:56:10: error: 'fa' was not declared in this scope; did you mean 'fp'?
   56 |     iota(fa+1,fa+n+1,1);
      |          ^~
      |          fp
Main.cpp:57:10: error: 'ord' was not declared in this scope
   57 |     iota(ord+1,ord+n+1,1);
      |          ^~~
Main.cpp: In lambda function:
Main.cpp:59:16: error: 'a' was not declared in this scope
   59 |         return a[i]<a[j];
      |                ^
Main.cpp: In function 'int main()':
Main.cpp:63:20: error: 'adj' was not declared in this scope
   63 |         for(auto v:adj[u])if(a[u]>a[v]){
      |                    ^~~
Main.cpp:63:30: error: 'a' was not declared in this scope
   63 |         for(auto v:adj[u])if(a[u]>a[v]){
      |                              ^
Main.cpp:65:13: error: 'dp' was not declared in this scope; did you mean 'fp'?
   65 |             dp[u]=max(dp[u],dp[v]+dist(u,v));
      |             ^~
      |             fp
Main.cpp:69:13: error: 'dp' was not declared in this scope; did you mean 'fp'?
   69 |     cout << dp[ord[n]];
      |             ^~
      |             fp