oj.uz

Submission #524271

# Submission time Handle Problem Language Result Execution time Memory
524271 2022-02-09T01:05:46 Z Deepesson Swapping Cities (APIO20_swap) C++17
0 / 100
 864 ms 524292 KB 
#include <bits/stdc++.h>
#include "swap.h"
#define MAX 305000
int n,m;
typedef std::pair<int,int> pii;
typedef std::pair<int,pii> pip;
std::vector<pip> tmp;
std::vector<pii> con[MAX];
int pai[MAX];
bool acabou[MAX];
std::vector<int> candidatos[MAX];
int conexoes[MAX];
int fins[MAX];

int up[MAX][25];
int ph[MAX][25];
int prof[MAX];
void dfs(int pos,int prev,int peso,int depth){
    prof[pos]=depth;
    up[pos][0]=prev;
    ph[pos][0]=peso;
    for(auto&x:con[pos]){
        if(x.first==prev)continue;
        dfs(x.first,pos,x.second,depth+1);
    }
}
int find(int a){
    if(pai[a]==a)
        return a;
    return pai[a]=find(pai[a]);
}
int peso=0;
void Union(int a,int b){
    conexoes[a]++;
    conexoes[b]++;
    a=find(a);
    b=find(b);
    if(a==b)acabou[a]=true;
    else {
        con[a].push_back({b,peso});
        con[b].push_back({a,peso});
        pai[b]=a;
        for(auto&x:candidatos[b]){
            candidatos[a].push_back(x);
        }
        acabou[a]=std::max(acabou[a],acabou[b]);
    }
    if(acabou[a]){
        for(auto&x:candidatos[a])fins[x]=peso;
        candidatos[a].clear();
        return;
    }
    int count=0;
    {
        std::vector<int> novo;
        for(auto&x:candidatos[a]){
            if(conexoes[x]==1)++count;
        }
    }
    if(count>2){
        for(auto&x:candidatos[a]){
            fins[x]=peso;
        }
        candidatos[a].clear();
    }
}
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){
        tmp.push_back({W[i],{U[i],V[i]}});
    }

    std::sort(tmp.begin(),tmp.end());

    for(auto&x:fins)x=1e9;

    for(int i=0;i!=N;++i){
        pai[i]=i;
        candidatos[i].push_back(i);
    }

    for(auto&x:tmp){
        peso=x.first;
        int u = x.second.first,v=x.second.second;
        Union(u,v);
    }

    dfs(0,-1,-1,0);

    for(int j=1;j!=25;++j){
        for(int i=0;i!=N;++i){
            if(up[i][j-1]==-1){
                up[i][j]=-1;
                continue;
            }
            up[i][j]=up[up[i][j-1]][j-1];
            ph[i][j]=std::max(ph[up[i][j-1]][j-1],ph[i][j-1]);
        }
    }
   /* for(int i=0;i!=N;++i){
        std::cout<<fins[i]<<" ";
    }
    std::cout<<"\n";*/
}

int lcaval(int x,int y){
    if(prof[y]<prof[x])std::swap(x,y);
    int ans=0;
    for(int i=24;i!=-1;--i){
        int prox = up[y][i];
        if(prox==-1)continue;
        if(prof[prox]>=prof[x]){
            ans=std::max(ans,ph[y][i]);
            y=prox;
        }
    }
    assert(prof[x]==prof[y]);
   /// std::cout<<x<<" "<<y<<"preprof\n";
    for(int i=24;i!=-1;--i){
        int a = up[y][i];
        int b = up[x][i];
        if(a==-1||b==-1)continue;
        if(a!=b){
            ans=std::max(ans,ph[y][i]);
            ans=std::max(ans,ph[x][i]);
            x=b;
            y=a;
        }
    }
  ///  std::cout<<x<<" "<<y<<"<-\n";
    if(x!=y){
        ans=std::max(ans,ph[y][0]);
        ans=std::max(ans,ph[x][0]);
        x=up[x][0];
        y=up[y][0];
    }
    ///assert(x==y);
  ///  std::cout<<"Retorna "<<ans<<"\n";
  ///  std::cout<<x<<" "<<y<<"\n";
    return ans;
}

int getMinimumFuelCapacity(int X, int Y) {
  if(fins[X]==1e9&&fins[Y]==1e9)return -1;
  ///Proxima etapa: Achar o peso minimo entre o caminho de X e Y, a resposta sera max(min(fins[X],fins[Y]),caminho)
  int ans = std::min(fins[X],fins[Y]);
  return std::max(ans,lcaval(X,Y));
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15820 KB Output is correct
2 Correct 9 ms 15820 KB Output is correct
3 Correct 9 ms 15820 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 11 ms 16080 KB Output is correct
6 Correct 12 ms 16076 KB Output is correct
7 Correct 10 ms 16144 KB Output is correct
8 Correct 11 ms 16832 KB Output is correct
9 Correct 121 ms 45396 KB Output is correct
10 Correct 173 ms 51724 KB Output is correct
11 Correct 173 ms 51428 KB Output is correct
12 Correct 162 ms 53548 KB Output is correct
13 Runtime error 864 ms 524292 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15820 KB Output is correct
2 Correct 9 ms 15820 KB Output is correct
3 Incorrect 203 ms 48440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15820 KB Output is correct
2 Correct 9 ms 15820 KB Output is correct
3 Correct 9 ms 15820 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 11 ms 16080 KB Output is correct
6 Correct 12 ms 16076 KB Output is correct
7 Correct 10 ms 16144 KB Output is correct
8 Correct 11 ms 16832 KB Output is correct
9 Correct 8 ms 15800 KB Output is correct
10 Correct 10 ms 16108 KB Output is correct
11 Incorrect 10 ms 16204 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15800 KB Output is correct
2 Correct 8 ms 15820 KB Output is correct
3 Correct 9 ms 15820 KB Output is correct
4 Correct 9 ms 15820 KB Output is correct
5 Correct 9 ms 15948 KB Output is correct
6 Correct 11 ms 16080 KB Output is correct
7 Correct 12 ms 16076 KB Output is correct
8 Correct 10 ms 16144 KB Output is correct
9 Correct 11 ms 16832 KB Output is correct
10 Correct 121 ms 45396 KB Output is correct
11 Correct 173 ms 51724 KB Output is correct
12 Correct 173 ms 51428 KB Output is correct
13 Correct 162 ms 53548 KB Output is correct
14 Runtime error 864 ms 524292 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15820 KB Output is correct
2 Correct 9 ms 15820 KB Output is correct
3 Correct 9 ms 15820 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 11 ms 16080 KB Output is correct
6 Correct 12 ms 16076 KB Output is correct
7 Correct 10 ms 16144 KB Output is correct
8 Correct 11 ms 16832 KB Output is correct
9 Correct 121 ms 45396 KB Output is correct
10 Correct 173 ms 51724 KB Output is correct
11 Correct 173 ms 51428 KB Output is correct
12 Correct 162 ms 53548 KB Output is correct
13 Runtime error 864 ms 524292 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15800 KB Output is correct
2 Correct 8 ms 15820 KB Output is correct
3 Correct 9 ms 15820 KB Output is correct
4 Correct 9 ms 15820 KB Output is correct
5 Correct 9 ms 15948 KB Output is correct
6 Correct 11 ms 16080 KB Output is correct
7 Correct 12 ms 16076 KB Output is correct
8 Correct 10 ms 16144 KB Output is correct
9 Correct 11 ms 16832 KB Output is correct
10 Correct 121 ms 45396 KB Output is correct
11 Correct 173 ms 51724 KB Output is correct
12 Correct 173 ms 51428 KB Output is correct
13 Correct 162 ms 53548 KB Output is correct
14 Runtime error 864 ms 524292 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -