Submission #409870

#	Time	Username	Problem	Language	Result	Execution time	Memory
409870		Ahmad_Hasan	Swapping Cities (APIO20_swap)	C++17	0 / 100	2104 ms	292792 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
vector<vector<pair<int,int> > >adj;
vector<vector<int> >par,dis,mn;
vector<int>dep;
vector<vector<int> >mnaf;
int dfs(int cr=0,int pr=-1,int d=-1,int m=INT_MAX){
    par[cr][0]=pr;
    for(int i=1;i<30;i++){
        if(par[cr][i-1]==-1)break;
        par[cr][i]=par[par[cr][i-1]][i-1];
    }
    dis[cr][0]=d;
    for(int i=1;i<30;i++){
        if(par[cr][i-1]==-1)break;
        dis[cr][i]=dis[par[cr][i-1]][i-1];
    }
    mn[cr][0]=m;
    for(int i=1;i<30;i++){
        if(par[cr][i-1]==-1)break;
        mn[cr][i]=mn[par[cr][i-1]][i-1];
    }

    if(pr==-1)dep[cr]=0;
    else dep[cr]=dep[pr]+1;

    for(int i=0;i<adj[cr].size();i++){
        if(adj[cr][i].first!=pr){
            if(adj[cr][i].second<mnaf[cr][0]){
                mnaf[cr][1]=mnaf[cr][0];
                mnaf[cr][0]=adj[cr][i].second;
            }else{
                mnaf[cr][1]=adj[cr][i].second;
            }
        }

    }
    for(int i=0;i<adj[cr].size();i++){
        if(adj[cr][i].first!=pr){
            dfs(adj[cr][i].first,cr,adj[cr][i].second,(mnaf[cr][0]==adj[cr][i].second)?mnaf[cr][1]:mnaf[cr][0]);
        }

    }
    return 0;
}
void init (int n,int m,vector<int>u,vector<int>v,vector<int>w){

    adj.resize(n);
    for(int i=0;i<m;i++){
        adj[u[i]].push_back({v[i],w[i]});
        adj[v[i]].push_back({u[i],w[i]});
    }
    par=dis=vector<vector<int> >(n,vector<int>(32,-1));
    mn=vector<vector<int> >(n,vector<int>(32,INT_MAX));
    dep=vector<int>(n,INT_MAX);
    mnaf=vector<vector<int> >(n,vector<int>(2,INT_MAX));

    dfs();/**
    for(int i=0;i<n;i++){
        for(int j=0;j<10;j++)
            cout<<mn[i][j]<<' ';
        cout<<'\n';
    }

*/
}
int getMinimumFuelCapacity(int x,int y){
    return -1;
}/**
int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);

    init(5,4,{0,0,0,1},{1,2,3,4},{5,5,3,2});



  return 0;
}*/

Compilation message (stderr)

swap.cpp: In function 'int dfs(int, int, int, int)':
swap.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<adj[cr].size();i++){
      |                 ~^~~~~~~~~~~~~~~
swap.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<adj[cr].size();i++){
      |                 ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27