oj.uz

Submission #409870

# Submission time Handle Problem Language Result Execution time Memory
409870 2021-05-21T17:40:32 Z Ahmad_Hasan Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 292792 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 2 ms 792 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 210 ms 51908 KB Output is correct
10 Correct 271 ms 64324 KB Output is correct
11 Correct 255 ms 62916 KB Output is correct
12 Correct 290 ms 66840 KB Output is correct
13 Correct 314 ms 67916 KB Output is correct
14 Correct 208 ms 51524 KB Output is correct
15 Correct 349 ms 66492 KB Output is correct
16 Correct 333 ms 63604 KB Output is correct
17 Correct 361 ms 69656 KB Output is correct
18 Correct 348 ms 68780 KB Output is correct
19 Execution timed out 2093 ms 58200 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 174 ms 62364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 2 ms 792 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Execution timed out 2104 ms 292792 KB Time limit exceeded

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2104 ms 292792 KB Time limit exceeded

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 2 ms 792 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 210 ms 51908 KB Output is correct
10 Correct 271 ms 64324 KB Output is correct
11 Correct 255 ms 62916 KB Output is correct
12 Correct 290 ms 66840 KB Output is correct
13 Correct 314 ms 67916 KB Output is correct
14 Correct 208 ms 51524 KB Output is correct
15 Correct 349 ms 66492 KB Output is correct
16 Correct 333 ms 63604 KB Output is correct
17 Correct 361 ms 69656 KB Output is correct
18 Correct 348 ms 68780 KB Output is correct
19 Incorrect 174 ms 62364 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2104 ms 292792 KB Time limit exceeded