oj.uz

Submission #952405

# Submission time Handle Problem Language Result Execution time Memory
952405 2024-03-23T19:03:57 Z hyforces Swapping Cities (APIO20_swap) C++14
13 / 100
 387 ms 48524 KB 
#include<bits/stdc++.h>
#include"swap.h"
using namespace std;
#define N 100100
#define J 18
#define inf 0x3f3f3f3f
vector<pair<int,int>>adj[N];
int parent[N],fae[N];
pair<int,int>jump[N][J];
int tin[N],tout[N],t;
void dfs(int u,int fa){
    tin[u]=++t;
    jump[u][0]={parent[u],fae[u]};
    for(int a=1;a<J;++a){
        jump[u][a]={jump[jump[u][a-1].first][a-1].first,max({jump[u][a-1].second,jump[jump[u][a-1].first][a-1].second})};
    }
    for(auto a:adj[u]){
        if(a.first==fa)continue;
        fae[a.first]=a.second;
        parent[a.first]=u;
        dfs(a.first,u);
    }
    tout[u]=t;
}
bool isanc(int u,int v){
    return tin[u]<=tin[v]&&tout[v]<=tout[u];
}
int get(int u,int v){
    int ret=0;
    for(int a=J-1;a>=0;--a){
        if(!isanc(jump[u][a].first,v)){
            ret=max(ret,jump[u][a].second);
            u=jump[u][a].first;
        }
    }
    for(int a=J-1;a>=0;--a){
        if(!isanc(jump[v][a].first,u)){
            ret=max(ret,jump[v][a].second);
            v=jump[v][a].first;
        }
    }
    if(u==v)return ret;
    if(parent[u]==v)return max(ret,fae[u]);
    if(parent[v]==u)return max(ret,fae[v]);
    return max({ret,fae[u],fae[v]});
}

int deg[N],kt[N];
int ktv=0;

int getMinimumFuelCapacity(int u,int v){
    int ret=max(get(u,v),min(kt[u],kt[v]));
    return ret==inf?-1:max(ret,0);
}

struct DSU{
    bool mark[N];
    int fa[N];
    vector<int>buk[N];
    void activate(int u){
        if(mark[u])return;
        mark[u]=true;
        for(auto a:buk[u])kt[a]=ktv;
    }
    int root(int u){return fa[u]==u?u:fa[u]=root(fa[u]);}
    bool merge(int u,int v){
        u=root(u),v=root(v);
        if(u==v){
            activate(u);
            return false;
        }
        if(mark[u])activate(v);
        if(mark[v])activate(u);
        mark[u]|=mark[v];
        if(buk[u].size()<buk[v].size())buk[u].swap(buk[v]);
        for(auto a:buk[v])buk[u].push_back(a);
        buk[v].clear();
        fa[v]=u;
        return true;
    }
    void init(){
        for(int a=0;a<N;++a){
            fa[a]=a;
            buk[a].push_back(a);
        }
    }
}calc;

void init(int n,int m,vector<int>U,vector<int>V,vector<int>W){
    memset(kt,0x3f,sizeof(kt));
    calc.init();
    vector<int>ord;
    for(int a=0;a<m;++a)ord.push_back(a);
    sort(ord.begin(),ord.end(),[&](const int&x,const int&y)->bool{return W[x]<W[y];});
    for(int i=0;i<m;++i){int a=ord[i];
        ktv=W[a];
        if((++deg[U[a]])>=3)calc.activate(U[a]);
        if((++deg[V[a]])>=3)calc.activate(V[a]);
        if(calc.merge(U[a],V[a])){
            adj[U[a]].push_back({V[a],W[a]});
            adj[V[a]].push_back({U[a],W[a]});
        }
    }
    dfs(0,0);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12636 KB Output is correct
2 Correct 7 ms 12636 KB Output is correct
3 Correct 7 ms 12636 KB Output is correct
4 Correct 7 ms 12632 KB Output is correct
5 Correct 6 ms 12888 KB Output is correct
6 Correct 6 ms 12892 KB Output is correct
7 Correct 7 ms 12888 KB Output is correct
8 Correct 6 ms 12892 KB Output is correct
9 Correct 99 ms 36220 KB Output is correct
10 Correct 127 ms 41360 KB Output is correct
11 Correct 118 ms 40408 KB Output is correct
12 Correct 142 ms 42612 KB Output is correct
13 Correct 111 ms 41736 KB Output is correct
14 Correct 101 ms 35844 KB Output is correct
15 Correct 332 ms 45548 KB Output is correct
16 Correct 308 ms 42984 KB Output is correct
17 Correct 348 ms 48524 KB Output is correct
18 Correct 265 ms 44040 KB Output is correct
19 Correct 89 ms 22864 KB Output is correct
20 Correct 338 ms 45676 KB Output is correct
21 Correct 342 ms 44264 KB Output is correct
22 Correct 387 ms 47168 KB Output is correct
23 Correct 344 ms 44776 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12636 KB Output is correct
2 Correct 7 ms 12636 KB Output is correct
3 Correct 169 ms 37560 KB Output is correct
4 Correct 146 ms 38316 KB Output is correct
5 Correct 185 ms 38120 KB Output is correct
6 Correct 135 ms 38328 KB Output is correct
7 Correct 155 ms 38284 KB Output is correct
8 Correct 133 ms 37392 KB Output is correct
9 Correct 140 ms 38112 KB Output is correct
10 Correct 157 ms 37408 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12636 KB Output is correct
2 Correct 7 ms 12636 KB Output is correct
3 Correct 7 ms 12636 KB Output is correct
4 Correct 7 ms 12632 KB Output is correct
5 Correct 6 ms 12888 KB Output is correct
6 Correct 6 ms 12892 KB Output is correct
7 Correct 7 ms 12888 KB Output is correct
8 Correct 6 ms 12892 KB Output is correct
9 Correct 6 ms 12636 KB Output is correct
10 Correct 6 ms 12892 KB Output is correct
11 Incorrect 6 ms 12940 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12636 KB Output is correct
2 Correct 5 ms 12636 KB Output is correct
3 Correct 7 ms 12636 KB Output is correct
4 Correct 7 ms 12636 KB Output is correct
5 Correct 7 ms 12632 KB Output is correct
6 Correct 6 ms 12888 KB Output is correct
7 Correct 6 ms 12892 KB Output is correct
8 Correct 7 ms 12888 KB Output is correct
9 Correct 6 ms 12892 KB Output is correct
10 Correct 99 ms 36220 KB Output is correct
11 Correct 127 ms 41360 KB Output is correct
12 Correct 118 ms 40408 KB Output is correct
13 Correct 142 ms 42612 KB Output is correct
14 Correct 111 ms 41736 KB Output is correct
15 Correct 6 ms 12892 KB Output is correct
16 Incorrect 6 ms 12940 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12636 KB Output is correct
2 Correct 7 ms 12636 KB Output is correct
3 Correct 7 ms 12636 KB Output is correct
4 Correct 7 ms 12632 KB Output is correct
5 Correct 6 ms 12888 KB Output is correct
6 Correct 6 ms 12892 KB Output is correct
7 Correct 7 ms 12888 KB Output is correct
8 Correct 6 ms 12892 KB Output is correct
9 Correct 99 ms 36220 KB Output is correct
10 Correct 127 ms 41360 KB Output is correct
11 Correct 118 ms 40408 KB Output is correct
12 Correct 142 ms 42612 KB Output is correct
13 Correct 111 ms 41736 KB Output is correct
14 Correct 101 ms 35844 KB Output is correct
15 Correct 332 ms 45548 KB Output is correct
16 Correct 308 ms 42984 KB Output is correct
17 Correct 348 ms 48524 KB Output is correct
18 Correct 265 ms 44040 KB Output is correct
19 Correct 169 ms 37560 KB Output is correct
20 Correct 146 ms 38316 KB Output is correct
21 Correct 185 ms 38120 KB Output is correct
22 Correct 135 ms 38328 KB Output is correct
23 Correct 155 ms 38284 KB Output is correct
24 Correct 133 ms 37392 KB Output is correct
25 Correct 140 ms 38112 KB Output is correct
26 Correct 157 ms 37408 KB Output is correct
27 Correct 6 ms 12892 KB Output is correct
28 Incorrect 6 ms 12940 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12636 KB Output is correct
2 Correct 5 ms 12636 KB Output is correct
3 Correct 7 ms 12636 KB Output is correct
4 Correct 7 ms 12636 KB Output is correct
5 Correct 7 ms 12632 KB Output is correct
6 Correct 6 ms 12888 KB Output is correct
7 Correct 6 ms 12892 KB Output is correct
8 Correct 7 ms 12888 KB Output is correct
9 Correct 6 ms 12892 KB Output is correct
10 Correct 99 ms 36220 KB Output is correct
11 Correct 127 ms 41360 KB Output is correct
12 Correct 118 ms 40408 KB Output is correct
13 Correct 142 ms 42612 KB Output is correct
14 Correct 111 ms 41736 KB Output is correct
15 Correct 101 ms 35844 KB Output is correct
16 Correct 332 ms 45548 KB Output is correct
17 Correct 308 ms 42984 KB Output is correct
18 Correct 348 ms 48524 KB Output is correct
19 Correct 265 ms 44040 KB Output is correct
20 Correct 169 ms 37560 KB Output is correct
21 Correct 146 ms 38316 KB Output is correct
22 Correct 185 ms 38120 KB Output is correct
23 Correct 135 ms 38328 KB Output is correct
24 Correct 155 ms 38284 KB Output is correct
25 Correct 133 ms 37392 KB Output is correct
26 Correct 140 ms 38112 KB Output is correct
27 Correct 157 ms 37408 KB Output is correct
28 Correct 6 ms 12892 KB Output is correct
29 Incorrect 6 ms 12940 KB Output isn't correct
30 Halted 0 ms 0 KB -