oj.uz

Submission #982110

# Submission time Handle Problem Language Result Execution time Memory
982110 2024-05-13T20:42:27 Z Abito Swapping Cities (APIO20_swap) C++17
7 / 100
 456 ms 524288 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define ep insert
#define pb push_back
using namespace std;
const int NN=4e5+5;
int n,m,c,C=INT_MAX,dis[NN],lg[NN],f[NN];
vector<pair<int,int>> adj[NN];
pair<int,int> st[25][NN],par[25][NN];
bool cmp(pair<int,int> x,pair<int,int> y){
    return x.S<y.S;
}
void dfs(int x,int p){
    dis[x]=dis[p]+1;
    st[0][++c]={dis[x],x};
    f[x]=c;
    for (auto u:adj[x]){
        if (u.F==p) continue;
        par[0][u.F]={x,u.S};
        dfs(u.F,x);
        st[0][++c]={dis[x],x};
    }return;
}
void build(){
    for (int i=1;i<25;i++) for (int j=1;j+(1<<i)<=2*n;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
    for (int i=1;i<25;i++){
        for (int j=1;j<=n;j++){
            par[i][j].F=par[i-1][par[i-1][j].F].F;
            par[i][j].S=max(par[i-1][j].S,par[i-1][par[i-1][j].F].S);
        }
    }return;
}
int query(int l,int r){
    if (l>r) swap(l,r);
    int i=lg[r-l+1];
    return min(st[i][l],st[i][r-(1<<i)+1]).S;
}
void init(int N, int M,
          vector<int> U, vector<int> V, vector<int> W) {
    for (int i=2;i<NN;i++) lg[i]=lg[i/2]+1;
    n=N,m=M;dis[0]=-1;
    for (int i=0;i<m;i++){
        adj[U[i]+1].pb({V[i]+1,W[i]});
        adj[V[i]+1].pb({U[i]+1,W[i]});
    }
    for (int i=1;i<=n;i++){
        if (adj[i].size()<3) continue;
        sort(adj[i].begin(),adj[i].end(),cmp);
        C=min(C,adj[i][2].S);
    }
    dfs(1,0);
    build();
    return;
}

int getMinimumFuelCapacity(int x, int y) {
    x++;y++;
    int lca=query(f[x],f[y]);
    int ans=C,ansx=0,ansy=0;
    for (int i=0;i<25;i++) if ((dis[x]-dis[lca])&(1<<i)) ansx=max(ansx,par[i][x].S),x=par[i][x].F;
    for (int i=0;i<25;i++) if ((dis[y]-dis[lca])&(1<<i)) ansy=max(ansy,par[i][y].S),y=par[i][y].F;
    ans=max(ans,max(ansx,ansy));
    if (ans==INT_MAX) return -1;
    return ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 66908 KB Output is correct
2 Correct 10 ms 68956 KB Output is correct
3 Correct 9 ms 68956 KB Output is correct
4 Correct 20 ms 83292 KB Output is correct
5 Correct 13 ms 85400 KB Output is correct
6 Correct 11 ms 85592 KB Output is correct
7 Correct 11 ms 85488 KB Output is correct
8 Correct 11 ms 85848 KB Output is correct
9 Correct 84 ms 139748 KB Output is correct
10 Correct 65 ms 146772 KB Output is correct
11 Correct 69 ms 146336 KB Output is correct
12 Correct 74 ms 147024 KB Output is correct
13 Correct 67 ms 148560 KB Output is correct
14 Correct 74 ms 139556 KB Output is correct
15 Correct 227 ms 150868 KB Output is correct
16 Correct 219 ms 149312 KB Output is correct
17 Correct 220 ms 152664 KB Output is correct
18 Correct 280 ms 151536 KB Output is correct
19 Runtime error 456 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 66908 KB Output is correct
2 Correct 10 ms 68956 KB Output is correct
3 Correct 139 ms 147592 KB Output is correct
4 Correct 133 ms 147760 KB Output is correct
5 Correct 135 ms 147928 KB Output is correct
6 Correct 131 ms 147524 KB Output is correct
7 Correct 134 ms 148036 KB Output is correct
8 Correct 142 ms 147732 KB Output is correct
9 Correct 130 ms 147828 KB Output is correct
10 Correct 130 ms 147480 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 66908 KB Output is correct
2 Correct 10 ms 68956 KB Output is correct
3 Correct 9 ms 68956 KB Output is correct
4 Correct 20 ms 83292 KB Output is correct
5 Correct 13 ms 85400 KB Output is correct
6 Correct 11 ms 85592 KB Output is correct
7 Correct 11 ms 85488 KB Output is correct
8 Correct 11 ms 85848 KB Output is correct
9 Runtime error 261 ms 524288 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 261 ms 524288 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 25 ms 66908 KB Output is correct
2 Correct 10 ms 68956 KB Output is correct
3 Correct 9 ms 68956 KB Output is correct
4 Correct 20 ms 83292 KB Output is correct
5 Correct 13 ms 85400 KB Output is correct
6 Correct 11 ms 85592 KB Output is correct
7 Correct 11 ms 85488 KB Output is correct
8 Correct 11 ms 85848 KB Output is correct
9 Correct 84 ms 139748 KB Output is correct
10 Correct 65 ms 146772 KB Output is correct
11 Correct 69 ms 146336 KB Output is correct
12 Correct 74 ms 147024 KB Output is correct
13 Correct 67 ms 148560 KB Output is correct
14 Correct 74 ms 139556 KB Output is correct
15 Correct 227 ms 150868 KB Output is correct
16 Correct 219 ms 149312 KB Output is correct
17 Correct 220 ms 152664 KB Output is correct
18 Correct 280 ms 151536 KB Output is correct
19 Correct 139 ms 147592 KB Output is correct
20 Correct 133 ms 147760 KB Output is correct
21 Correct 135 ms 147928 KB Output is correct
22 Correct 131 ms 147524 KB Output is correct
23 Correct 134 ms 148036 KB Output is correct
24 Correct 142 ms 147732 KB Output is correct
25 Correct 130 ms 147828 KB Output is correct
26 Correct 130 ms 147480 KB Output is correct
27 Correct 11 ms 85336 KB Output is correct
28 Correct 12 ms 85596 KB Output is correct
29 Correct 11 ms 85472 KB Output is correct
30 Correct 11 ms 85336 KB Output is correct
31 Correct 11 ms 85336 KB Output is correct
32 Incorrect 12 ms 85596 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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