oj.uz

Submission #524270

# Submission time Handle Problem Language Result Execution time Memory
524270 2022-02-09T01:05:13 Z Deepesson Swapping Cities (APIO20_swap) C++17
0 / 100
 829 ms 524292 KB 
#include <bits/stdc++.h>
#include "swap.h"
#define MAX 105000
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 3 ms 5580 KB Output is correct
2 Correct 3 ms 5620 KB Output is correct
3 Correct 3 ms 5620 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 6020 KB Output is correct
6 Correct 4 ms 5892 KB Output is correct
7 Correct 4 ms 6016 KB Output is correct
8 Correct 4 ms 6656 KB Output is correct
9 Correct 106 ms 36852 KB Output is correct
10 Correct 133 ms 43676 KB Output is correct
11 Correct 140 ms 43184 KB Output is correct
12 Correct 141 ms 45548 KB Output is correct
13 Runtime error 829 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 3 ms 5580 KB Output is correct
2 Correct 3 ms 5620 KB Output is correct
3 Incorrect 196 ms 42204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5580 KB Output is correct
2 Correct 3 ms 5620 KB Output is correct
3 Correct 3 ms 5620 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 6020 KB Output is correct
6 Correct 4 ms 5892 KB Output is correct
7 Correct 4 ms 6016 KB Output is correct
8 Correct 4 ms 6656 KB Output is correct
9 Correct 3 ms 5580 KB Output is correct
10 Correct 4 ms 5888 KB Output is correct
11 Incorrect 4 ms 5956 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5580 KB Output is correct
2 Correct 3 ms 5580 KB Output is correct
3 Correct 3 ms 5620 KB Output is correct
4 Correct 3 ms 5620 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 4 ms 6020 KB Output is correct
7 Correct 4 ms 5892 KB Output is correct
8 Correct 4 ms 6016 KB Output is correct
9 Correct 4 ms 6656 KB Output is correct
10 Correct 106 ms 36852 KB Output is correct
11 Correct 133 ms 43676 KB Output is correct
12 Correct 140 ms 43184 KB Output is correct
13 Correct 141 ms 45548 KB Output is correct
14 Runtime error 829 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 3 ms 5580 KB Output is correct
2 Correct 3 ms 5620 KB Output is correct
3 Correct 3 ms 5620 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 6020 KB Output is correct
6 Correct 4 ms 5892 KB Output is correct
7 Correct 4 ms 6016 KB Output is correct
8 Correct 4 ms 6656 KB Output is correct
9 Correct 106 ms 36852 KB Output is correct
10 Correct 133 ms 43676 KB Output is correct
11 Correct 140 ms 43184 KB Output is correct
12 Correct 141 ms 45548 KB Output is correct
13 Runtime error 829 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 3 ms 5580 KB Output is correct
2 Correct 3 ms 5580 KB Output is correct
3 Correct 3 ms 5620 KB Output is correct
4 Correct 3 ms 5620 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 4 ms 6020 KB Output is correct
7 Correct 4 ms 5892 KB Output is correct
8 Correct 4 ms 6016 KB Output is correct
9 Correct 4 ms 6656 KB Output is correct
10 Correct 106 ms 36852 KB Output is correct
11 Correct 133 ms 43676 KB Output is correct
12 Correct 140 ms 43184 KB Output is correct
13 Correct 141 ms 45548 KB Output is correct
14 Runtime error 829 ms 524292 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -