oj.uz

Submission #524273

# Submission time Handle Problem Language Result Execution time Memory
524273 2022-02-09T01:09:00 Z Deepesson Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 51744 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;
        if(candidatos[b]>candidatos[a])std::swap(candidatos[a],candidatos[b]);
        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 11 ms 15820 KB Output is correct
3 Correct 10 ms 15820 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 9 ms 16076 KB Output is correct
6 Correct 9 ms 16120 KB Output is correct
7 Correct 9 ms 16076 KB Output is correct
8 Correct 9 ms 16100 KB Output is correct
9 Correct 108 ms 44268 KB Output is correct
10 Correct 149 ms 50068 KB Output is correct
11 Correct 154 ms 49652 KB Output is correct
12 Correct 148 ms 51744 KB Output is correct
13 Execution timed out 2087 ms 29724 KB Time limit exceeded
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 11 ms 15820 KB Output is correct
3 Incorrect 221 ms 48396 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 11 ms 15820 KB Output is correct
3 Correct 10 ms 15820 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 9 ms 16076 KB Output is correct
6 Correct 9 ms 16120 KB Output is correct
7 Correct 9 ms 16076 KB Output is correct
8 Correct 9 ms 16100 KB Output is correct
9 Correct 9 ms 15848 KB Output is correct
10 Correct 9 ms 16064 KB Output is correct
11 Incorrect 9 ms 16144 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15848 KB Output is correct
2 Correct 8 ms 15820 KB Output is correct
3 Correct 11 ms 15820 KB Output is correct
4 Correct 10 ms 15820 KB Output is correct
5 Correct 9 ms 15948 KB Output is correct
6 Correct 9 ms 16076 KB Output is correct
7 Correct 9 ms 16120 KB Output is correct
8 Correct 9 ms 16076 KB Output is correct
9 Correct 9 ms 16100 KB Output is correct
10 Correct 108 ms 44268 KB Output is correct
11 Correct 149 ms 50068 KB Output is correct
12 Correct 154 ms 49652 KB Output is correct
13 Correct 148 ms 51744 KB Output is correct
14 Execution timed out 2087 ms 29724 KB Time limit exceeded
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 11 ms 15820 KB Output is correct
3 Correct 10 ms 15820 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 9 ms 16076 KB Output is correct
6 Correct 9 ms 16120 KB Output is correct
7 Correct 9 ms 16076 KB Output is correct
8 Correct 9 ms 16100 KB Output is correct
9 Correct 108 ms 44268 KB Output is correct
10 Correct 149 ms 50068 KB Output is correct
11 Correct 154 ms 49652 KB Output is correct
12 Correct 148 ms 51744 KB Output is correct
13 Execution timed out 2087 ms 29724 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15848 KB Output is correct
2 Correct 8 ms 15820 KB Output is correct
3 Correct 11 ms 15820 KB Output is correct
4 Correct 10 ms 15820 KB Output is correct
5 Correct 9 ms 15948 KB Output is correct
6 Correct 9 ms 16076 KB Output is correct
7 Correct 9 ms 16120 KB Output is correct
8 Correct 9 ms 16076 KB Output is correct
9 Correct 9 ms 16100 KB Output is correct
10 Correct 108 ms 44268 KB Output is correct
11 Correct 149 ms 50068 KB Output is correct
12 Correct 154 ms 49652 KB Output is correct
13 Correct 148 ms 51744 KB Output is correct
14 Execution timed out 2087 ms 29724 KB Time limit exceeded
15 Halted 0 ms 0 KB -