oj.uz

Submission #532890

# Submission time Handle Problem Language Result Execution time Memory
532890 2022-03-04T07:41:19 Z ohohorz Swapping Cities (APIO20_swap) C++14
0 / 100
 1594 ms 524292 KB 
#include "swap.h"

#include <vector>
#include<set>
#include<algorithm>
#include<climits>
#include<map>
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;
    for(int i = 21;i >= 0;i--){
        if(!is_ans(up[u][i], v)) 
            u = up[u][i];
    }
    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) {
  X++, Y++;
  int lca = LCA(X, Y);
  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 2 ms 2632 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2672 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 4 ms 3160 KB Output is correct
6 Correct 3 ms 3148 KB Output is correct
7 Correct 4 ms 3160 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 278 ms 43868 KB Output is correct
10 Correct 386 ms 54372 KB Output is correct
11 Correct 347 ms 52940 KB Output is correct
12 Correct 371 ms 56112 KB Output is correct
13 Correct 356 ms 58188 KB Output is correct
14 Correct 309 ms 42992 KB Output is correct
15 Correct 609 ms 56172 KB Output is correct
16 Correct 586 ms 52848 KB Output is correct
17 Correct 612 ms 59848 KB Output is correct
18 Correct 674 ms 58272 KB Output is correct
19 Runtime error 1594 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 2 ms 2632 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Incorrect 337 ms 48660 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2632 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2672 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 4 ms 3160 KB Output is correct
6 Correct 3 ms 3148 KB Output is correct
7 Correct 4 ms 3160 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Runtime error 241 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 241 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 2 ms 2632 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2672 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 4 ms 3160 KB Output is correct
6 Correct 3 ms 3148 KB Output is correct
7 Correct 4 ms 3160 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 278 ms 43868 KB Output is correct
10 Correct 386 ms 54372 KB Output is correct
11 Correct 347 ms 52940 KB Output is correct
12 Correct 371 ms 56112 KB Output is correct
13 Correct 356 ms 58188 KB Output is correct
14 Correct 309 ms 42992 KB Output is correct
15 Correct 609 ms 56172 KB Output is correct
16 Correct 586 ms 52848 KB Output is correct
17 Correct 612 ms 59848 KB Output is correct
18 Correct 674 ms 58272 KB Output is correct
19 Incorrect 337 ms 48660 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 241 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -