oj.uz

Submission #524272

# Submission time Handle Problem Language Result Execution time Memory
524272 2022-02-09T01:06:49 Z Deepesson Swapping Cities (APIO20_swap) C++17
0 / 100
 880 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);
        }
        candidatos[b].clear();
        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 8 ms 15820 KB Output is correct
3 Correct 8 ms 15820 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 9 ms 16176 KB Output is correct
6 Correct 9 ms 16076 KB Output is correct
7 Correct 10 ms 16172 KB Output is correct
8 Correct 10 ms 16716 KB Output is correct
9 Correct 118 ms 45728 KB Output is correct
10 Correct 140 ms 51768 KB Output is correct
11 Correct 163 ms 51328 KB Output is correct
12 Correct 149 ms 53556 KB Output is correct
13 Runtime error 880 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 8 ms 15820 KB Output is correct
3 Incorrect 201 ms 48404 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 8 ms 15820 KB Output is correct
3 Correct 8 ms 15820 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 9 ms 16176 KB Output is correct
6 Correct 9 ms 16076 KB Output is correct
7 Correct 10 ms 16172 KB Output is correct
8 Correct 10 ms 16716 KB Output is correct
9 Correct 8 ms 15844 KB Output is correct
10 Correct 9 ms 16092 KB Output is correct
11 Incorrect 9 ms 16076 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 15844 KB Output is correct
2 Correct 8 ms 15820 KB Output is correct
3 Correct 8 ms 15820 KB Output is correct
4 Correct 8 ms 15820 KB Output is correct
5 Correct 9 ms 15948 KB Output is correct
6 Correct 9 ms 16176 KB Output is correct
7 Correct 9 ms 16076 KB Output is correct
8 Correct 10 ms 16172 KB Output is correct
9 Correct 10 ms 16716 KB Output is correct
10 Correct 118 ms 45728 KB Output is correct
11 Correct 140 ms 51768 KB Output is correct
12 Correct 163 ms 51328 KB Output is correct
13 Correct 149 ms 53556 KB Output is correct
14 Runtime error 880 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 8 ms 15820 KB Output is correct
3 Correct 8 ms 15820 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 9 ms 16176 KB Output is correct
6 Correct 9 ms 16076 KB Output is correct
7 Correct 10 ms 16172 KB Output is correct
8 Correct 10 ms 16716 KB Output is correct
9 Correct 118 ms 45728 KB Output is correct
10 Correct 140 ms 51768 KB Output is correct
11 Correct 163 ms 51328 KB Output is correct
12 Correct 149 ms 53556 KB Output is correct
13 Runtime error 880 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 15844 KB Output is correct
2 Correct 8 ms 15820 KB Output is correct
3 Correct 8 ms 15820 KB Output is correct
4 Correct 8 ms 15820 KB Output is correct
5 Correct 9 ms 15948 KB Output is correct
6 Correct 9 ms 16176 KB Output is correct
7 Correct 9 ms 16076 KB Output is correct
8 Correct 10 ms 16172 KB Output is correct
9 Correct 10 ms 16716 KB Output is correct
10 Correct 118 ms 45728 KB Output is correct
11 Correct 140 ms 51768 KB Output is correct
12 Correct 163 ms 51328 KB Output is correct
13 Correct 149 ms 53556 KB Output is correct
14 Runtime error 880 ms 524292 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -