oj.uz

Submission #973051

# Submission time Handle Problem Language Result Execution time Memory
973051 2024-05-01T12:56:23 Z Younis_Dwai Swapping Cities (APIO20_swap) C++14
17 / 100
 71 ms 30148 KB 
#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define in insert
#define F first
#define S second
vector<int> adj[100009];
int par1[100009],par[100009][21],depth[100009],cnt[100009],nxt=0,good[100009],val[1000009],done=0;
int get_par(int node){
    if(par1[node]==node) return node;
    return par1[node]=get_par(par1[node]);
}
void merg(int u,  int v ,int w){
     int uu=get_par(u);
     int vv=get_par(v);
     nxt++;
     val[nxt]=w;
     if(uu==vv){
        adj[nxt].pb(uu);
        cnt[u]++;
        cnt[v]++;
        good[nxt]=1;
        par1[uu]=nxt;
        return ;
     }
     adj[nxt].pb(uu);
     adj[nxt].pb(vv);
     cnt[u]++;
     cnt[v]++;
     par1[uu]=nxt;
     par1[vv]=nxt;
     if(cnt[u]>=3 || cnt[v]>=3) good[nxt]=1;
     return ;
}
void dfs(int node , int p){
     par[node][0]=p;
     for(int i=1;i<=20;i++) par[node][i]=par[par[node][i-1]][i-1];
     for(auto u : adj[node]){
         depth[u]=1+depth[node];
         dfs(u,node);
         good[node]|=good[u];
     }
     //cout<<" # "<<node<<' '<<good[node]<<' '<<val[node]<<endl;
     return ;
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
     nxt=N-1;
     for(int i=0;i<N+M;i++) par1[i]=i;
     vector<pair<int,pair<int,int>>> v;
     for(int i=0;i<M;i++){
         v.pb({W[i],{U[i],V[i]}});
     }
     sort(v.begin(),v.end());
     for(auto u : v){
         merg(u.S.F,u.S.S,u.F);
     }
     dfs(nxt,nxt);
     return ;
}
int lca(int u , int v){
    if(depth[v]>depth[u]) swap(u,v);
    for(int i=20;i>=0;i--) if(depth[u]-(1<<i)>=depth[v]) u=par[u][i];
    if(u==v) return u;
    for(int i=20;i>=0;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
    return par[u][0];
}
int getMinimumFuelCapacity(int X, int Y) {
    int lc=lca(X,Y);
    //cout<<" @ "<<X<<' '<<Y<<' '<<lc<<endl;
    if(good[lc]==1) return val[lc];
    for(int i=20;i>=0;i--) if(good[par[lc][i]]==0) lc=par[lc][i];
    lc=par[lc][0];
    if(good[lc]) return val[lc];
    return -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6064 KB Output is correct
2 Correct 1 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 6056 KB Output is correct
8 Correct 2 ms 5980 KB Output is correct
9 Runtime error 45 ms 24744 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6064 KB Output is correct
2 Correct 1 ms 5980 KB Output is correct
3 Runtime error 71 ms 30148 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6064 KB Output is correct
2 Correct 1 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 6056 KB Output is correct
8 Correct 2 ms 5980 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8028 KB Output is correct
14 Correct 2 ms 8028 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 3 ms 8028 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 3 ms 8280 KB Output is correct
19 Correct 2 ms 8028 KB Output is correct
20 Correct 2 ms 8028 KB Output is correct
21 Correct 2 ms 8188 KB Output is correct
22 Correct 3 ms 8284 KB Output is correct
23 Correct 2 ms 8028 KB Output is correct
24 Correct 3 ms 8284 KB Output is correct
25 Correct 3 ms 8284 KB Output is correct
26 Correct 3 ms 8284 KB Output is correct
27 Correct 2 ms 8028 KB Output is correct
28 Correct 3 ms 8364 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 6064 KB Output is correct
3 Correct 1 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 2 ms 6056 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Runtime error 45 ms 24744 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6064 KB Output is correct
2 Correct 1 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 6056 KB Output is correct
8 Correct 2 ms 5980 KB Output is correct
9 Runtime error 45 ms 24744 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 6064 KB Output is correct
3 Correct 1 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 2 ms 6056 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Runtime error 45 ms 24744 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -