Submission #835082

#	Time	Username	Problem	Language	Result	Execution time	Memory
835082		kwongweng	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	259 ms	51964 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second

const int N = 2e5+1;
vi g[N], d(N); int par[N][18];
void dfs(int u){
  for (int v : g[u]){
    if (par[u][0]==v) continue;
    par[v][0]=u; d[v]=d[u]+1; dfs(v);
  }
}

int dist(int U, int V){
  int u=U, v=V;
  int ans = d[u]+d[v];
  if (d[u]<d[v]) swap(u,v);
  int len=d[u]-d[v]; int cur=0;
  while (len>0){
    if (len%2==1) u=par[u][cur];
    len/=2; cur++;
  }
  if (u==v) return ans-2*d[u];
  ROF(i,17,0){
    if (par[u][i]==par[v][i]) continue;
    u=par[u][i]; v=par[v][i];
  }
  return ans-2*d[u]+2;
}


// DSU
// mx stores vertex with max height
vi h(N), p(N), r(N), mx(N);
int get(int a){
  if (p[a]==a) return a;
  return p[a]=get(p[a]);
}

void Union(int a, int b){
  int c=get(a),d=get(b);
  if (c==d) return;
  if (r[c]==r[d]) r[c]++;
  if (r[c]>r[d]){
    p[d]=c;
    if (h[mx[d]]>h[mx[c]]) mx[c]=mx[d];
  }else{
    p[c]=d;
    if (h[mx[c]]>h[mx[d]]) mx[d]=mx[c];
  }
}

void solve(){
  int n; cin>>n;
  FOR(i,1,n+1) cin>>h[i];
  FOR(i,0,n-1){
    int u,v; cin>>u>>v;
    g[u].pb(v); g[v].pb(u);
  }
  par[1][0]=1;
  dfs(1);
  FOR(j,1,18){
    FOR(i,1,n+1){
      par[i][j]=par[par[i][j-1]][j-1];
    }
  }
  FOR(i,1,n+1) {p[i]=i; mx[i]=i;}
  vii G[n+1];
  vii pos(n+1);
  FOR(i,1,n+1) pos[i]={h[i],i};
  sort(pos.begin(), pos.end());
  FOR(i,1,n+1){
    int u = pos[i].se;
    for (int v : g[u]){
      if (h[v]>h[u]) continue;
      int w = mx[get(v)];
      G[u].pb({w, dist(u,w)});
      //cout<<u<<" "<<w<<" "<<dist(u,w)<<"\n";
      Union(u,v);
    }
  }
  vector<ll> dis(n+1); vi used(n+1);
  queue<int> bfs; bfs.push(pos[n].se);
  while (!bfs.empty()){
    int u=bfs.front(); bfs.pop(); used[u]=1;
    for (ii edge :  G[u]){
      int v = edge.fi; if (used[v]) continue;
      used[v]=1; dis[v]=dis[u]+edge.se;
      bfs.push(v);
    }
  }
  ll mx=0; FOR(i,1,n+1) mx=max(mx,dis[i]);
  cout<<mx<<"\n";
}

int main(){
  ios::sync_with_stdio(false);
  if (fopen("input.txt", "r")) {
	  freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	}
  int TC = 1;
  //cin >> TC;
  FOR(i, 1, TC+1){
    //cout << "Case #" << i << ": ";
    solve();
  }
	
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:110:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |    freopen("input.txt", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:111:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26