oj.uz

Submission #414369

# Submission time Handle Problem Language Result Execution time Memory
414369 2021-05-30T11:37:43 Z prvocislo Swapping Cities (APIO20_swap) C++17
7 / 100
 2000 ms 524292 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5, logn = 18, inf = 1e9 + 5;
struct edge { int t, w; };
vector<vector<edge> > g(maxn);
bool cmp(edge a, edge b) { return a.w < b.w; }
int n, m;
vector<vector<int> > l(logn, vector<int>(maxn, 0)), mx(logn, vector<int>(maxn, 0));
vector<int> d(maxn, 0), cr(maxn, inf);
int lca(int u, int v)
{
  if (d[u] < d[v]) swap(u, v); // u je hlbsie
  int ans = 0;
  for (int i = logn - 1; i >= 0; i--) if ((1 << i) & (d[u] - d[v])) ans = max(ans, mx[i][u]), u = l[i][u];
  if (u == v) return ans;
  for (int i = logn - 1; i >= 0; i--) if(l[i][u] != l[i][v])
  {
    ans = max({ans, mx[i][u], mx[i][v]});
    u = l[i][u], v = l[i][v];
  }
  return max({ans, mx[0][u], mx[0][v]});
}
set<pair<int, int> > s;
void dfs(int u, int p = -1)
{
  sort(g[u].begin(), g[u].end(), cmp);
  if (g[u].size() >= 3) 
    s.insert({ g[u][2].w, u});
  for (int i = 1; i < logn; i++) l[i][u] = l[i-1][l[i-1][u]], mx[i][u] = max(mx[i-1][u], mx[i-1][l[i-1][u]]);
  for (const edge &i : g[u])
  {
    if (i.t == p) continue;
    l[0][i.t] = u, mx[0][i.t] = i.w;
    dfs(i.t, u);
  }
}
void init(int N, int M, vector<int> u, vector<int> v, vector<int> w) 
{ 
  n = N, m = M;
  for (int i =0;i<m;i++) g[u[i]].push_back({v[i], w[i]}), g[v[i]].push_back({u[i], w[i]});
  dfs(0, -1);
  while (!s.empty())
  {
    int d = s.begin()->first, u = s.begin()->second;
    s.erase(s.begin());
    if (cr[u] < inf) continue;
    cr[u] = d;
    for (edge i : g[u]) 
      if (cr[i.t] == inf) 
        s.insert({max(d, i.w), i.t});
  }
}
int getMinimumFuelCapacity(int x, int y) {
  int ans = max(lca(x, y), min(cr[x], cr[y]));
  return ans == inf ? -1 : ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17604 KB Output is correct
2 Correct 10 ms 17456 KB Output is correct
3 Correct 9 ms 17476 KB Output is correct
4 Correct 12 ms 17556 KB Output is correct
5 Correct 11 ms 17604 KB Output is correct
6 Correct 11 ms 17572 KB Output is correct
7 Correct 10 ms 17564 KB Output is correct
8 Correct 10 ms 17796 KB Output is correct
9 Correct 125 ms 27908 KB Output is correct
10 Correct 159 ms 31940 KB Output is correct
11 Correct 196 ms 31036 KB Output is correct
12 Correct 165 ms 32148 KB Output is correct
13 Correct 175 ms 34268 KB Output is correct
14 Correct 149 ms 27572 KB Output is correct
15 Correct 362 ms 34492 KB Output is correct
16 Correct 343 ms 32152 KB Output is correct
17 Correct 378 ms 36984 KB Output is correct
18 Correct 355 ms 35436 KB Output is correct
19 Execution timed out 2069 ms 440600 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17604 KB Output is correct
2 Correct 10 ms 17456 KB Output is correct
3 Correct 275 ms 32592 KB Output is correct
4 Correct 278 ms 33660 KB Output is correct
5 Correct 289 ms 33552 KB Output is correct
6 Correct 283 ms 33660 KB Output is correct
7 Correct 300 ms 33728 KB Output is correct
8 Correct 271 ms 33080 KB Output is correct
9 Correct 272 ms 33516 KB Output is correct
10 Correct 270 ms 32952 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17604 KB Output is correct
2 Correct 10 ms 17456 KB Output is correct
3 Correct 9 ms 17476 KB Output is correct
4 Correct 12 ms 17556 KB Output is correct
5 Correct 11 ms 17604 KB Output is correct
6 Correct 11 ms 17572 KB Output is correct
7 Correct 10 ms 17564 KB Output is correct
8 Correct 10 ms 17796 KB Output is correct
9 Runtime error 1423 ms 524292 KB Execution killed with signal 9

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1423 ms 524292 KB Execution killed with signal 9

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17604 KB Output is correct
2 Correct 10 ms 17456 KB Output is correct
3 Correct 9 ms 17476 KB Output is correct
4 Correct 12 ms 17556 KB Output is correct
5 Correct 11 ms 17604 KB Output is correct
6 Correct 11 ms 17572 KB Output is correct
7 Correct 10 ms 17564 KB Output is correct
8 Correct 10 ms 17796 KB Output is correct
9 Correct 125 ms 27908 KB Output is correct
10 Correct 159 ms 31940 KB Output is correct
11 Correct 196 ms 31036 KB Output is correct
12 Correct 165 ms 32148 KB Output is correct
13 Correct 175 ms 34268 KB Output is correct
14 Correct 149 ms 27572 KB Output is correct
15 Correct 362 ms 34492 KB Output is correct
16 Correct 343 ms 32152 KB Output is correct
17 Correct 378 ms 36984 KB Output is correct
18 Correct 355 ms 35436 KB Output is correct
19 Correct 275 ms 32592 KB Output is correct
20 Correct 278 ms 33660 KB Output is correct
21 Correct 289 ms 33552 KB Output is correct
22 Correct 283 ms 33660 KB Output is correct
23 Correct 300 ms 33728 KB Output is correct
24 Correct 271 ms 33080 KB Output is correct
25 Correct 272 ms 33516 KB Output is correct
26 Correct 270 ms 32952 KB Output is correct
27 Incorrect 11 ms 17572 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1423 ms 524292 KB Execution killed with signal 9