oj.uz

Submission #532901

# Submission time Handle Problem Language Result Execution time Memory
532901 2022-03-04T08:03:00 Z ohohorz Swapping Cities (APIO20_swap) C++17
0 / 100
 1694 ms 524292 KB 
#include "swap.h"

#include <vector>
#include<set>
#include<algorithm>
#include<climits>
#include<map>
#include<iostream>
using namespace std;

// #define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define sz(x) (int)x.size()

const int MAXN = 1e5 + 5;
const int INF = INT_MAX;
const int LOGN = 22;

int n, m;
vector< pair <int,int> > g[MAXN];
int up[MAXN][LOGN], mx[MAXN][LOGN], aux[MAXN][LOGN], tin[MAXN], tout[MAXN], timer, dist[MAXN], child[MAXN], par[MAXN];
map<pii,int> wt;

void dfs(int u,int p = 0,int d = 0){
    up[u][0] = p;
    tin[u] = ++timer;
    if(p != 0) child[p] = u;
    par[u] = p;
    dist[u] = d;
    if(p > 0) mx[u][0] = wt[mp(u, p)];
    for(int i = 0;i < sz(g[u]);i++){
        int v = g[u][i].first;
        if(v != p) dfs(v, u, d + 1);
    }
    tout[u] = ++timer;
}

bool is_ans(int u,int v){
    return (tin[u] <= tin[v] and tout[u] >= tout[v]);
}
int LCA(int u,int v){
    if(is_ans(u, v)) return u;
    if(is_ans(v, u)) return v;
    // cout<<"here\n";
    for(int i = 21;i >= 0;i--){
        if(!is_ans(up[u][i], v) and up[u][i]!=0) 
            u = up[u][i];
    }
    // cout<<u<<endl;
    return up[u][0];
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n = N,m = M;
  for(int i = 0;i < m;i++){
    int u = U[i] + 1;
    int v = V[i] + 1;
    g[u].pb(mp(v, W[i]));
    g[v].pb(mp(u, W[i]));
    wt[mp(u, v)] = W[i];
    wt[mp(v, u)] = W[i];
  }
  dfs(1);
  for(int i =1;i<=n;i++){
      if(child[i] == 0) continue;
      aux[child[i]][0] = INF;
      for(auto p:g[i]){
          int j = p.first;
          int w = p.second;
          if(j != child[i] and j!=par[i])
            aux[child[i]][0] = min(aux[child[i]][0], w);
      }
  }
  for(int j = 1;j < 22;j++){
      for(int i = 1;i<=n;i++){
          up[i][j] = up[up[i][j-1]][j-1];
          mx[i][j] = max(mx[i][j-1], mx[up[i][j-1]][j-1]);
          aux[i][j] = min(aux[i][j-1], aux[up[i][j-1]][j-1]);
      
    }
  }
  
  
}

int getMinimumFuelCapacity(int X, int Y) {
    // for(int i =1;i<=n;i++){
    //     cout<<i-1<<" -> :";
    //     for(int j = 0;j<5;j++){
    //         cout<<up[i][j]-1<<" ";
    //     }cout<<endl;
    // }
  X++, Y++;
  int lca = LCA(X, Y);
//   cout << X << " " << Y << " " << lca << endl;
  int x = X;
  int cur = 0;
  int mn =INF;
  for(int i = 21;i >= 0;i--){
      if(dist[lca]<dist[up[x][i]]){
          cur = max(cur, mx[x][i]);
          mn = min(mn, aux[x][i]);
          x = up[x][i];

      }
  }
  int y = Y;
  for(int i = 21;i >= 0;i--){
      if(dist[lca]<dist[up[y][i]]){
          cur = max(cur, mx[y][i]);
          mn = min(mn, aux[y][i]);
          y = up[y][i];
      }
  }
  if(mn == INF) return -1;
  return max(mn, cur);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 3 ms 2828 KB Output is correct
5 Correct 2 ms 3148 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 3 ms 3160 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 278 ms 43072 KB Output is correct
10 Correct 345 ms 53676 KB Output is correct
11 Correct 343 ms 52188 KB Output is correct
12 Correct 345 ms 55648 KB Output is correct
13 Correct 435 ms 57660 KB Output is correct
14 Correct 318 ms 42248 KB Output is correct
15 Correct 610 ms 55436 KB Output is correct
16 Correct 622 ms 52184 KB Output is correct
17 Correct 609 ms 59400 KB Output is correct
18 Correct 650 ms 57712 KB Output is correct
19 Runtime error 1694 ms 524292 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Incorrect 347 ms 48020 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 3 ms 2828 KB Output is correct
5 Correct 2 ms 3148 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 3 ms 3160 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Runtime error 245 ms 524292 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 245 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 3 ms 2828 KB Output is correct
5 Correct 2 ms 3148 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 3 ms 3160 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 278 ms 43072 KB Output is correct
10 Correct 345 ms 53676 KB Output is correct
11 Correct 343 ms 52188 KB Output is correct
12 Correct 345 ms 55648 KB Output is correct
13 Correct 435 ms 57660 KB Output is correct
14 Correct 318 ms 42248 KB Output is correct
15 Correct 610 ms 55436 KB Output is correct
16 Correct 622 ms 52184 KB Output is correct
17 Correct 609 ms 59400 KB Output is correct
18 Correct 650 ms 57712 KB Output is correct
19 Incorrect 347 ms 48020 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 245 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -