oj.uz

Submission #409875

# Submission time Handle Problem Language Result Execution time Memory
409875 2021-05-21T17:46:26 Z Ahmad_Hasan Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 291352 KB 
#include <bits/stdc++.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;
}
int f;
void init (int n,int m,vector<int>u,vector<int>v,vector<int>w){
	f=m<n;
    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){
  	if(f)
    return -1;
  return 0;
}/**
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:27: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]
   27 |     for(int i=0;i<adj[cr].size();i++){
      |                 ~^~~~~~~~~~~~~~~
swap.cpp:38: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]
   38 |     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 856 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 245 ms 51904 KB Output is correct
10 Correct 297 ms 64308 KB Output is correct
11 Correct 283 ms 62964 KB Output is correct
12 Correct 305 ms 66760 KB Output is correct
13 Correct 321 ms 67984 KB Output is correct
14 Correct 232 ms 51520 KB Output is correct
15 Correct 356 ms 66356 KB Output is correct
16 Correct 330 ms 63604 KB Output is correct
17 Correct 375 ms 69804 KB Output is correct
18 Correct 366 ms 68780 KB Output is correct
19 Execution timed out 2085 ms 48140 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 175 ms 62284 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 856 KB Output is correct
6 Correct 2 ms 844 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 2091 ms 291352 KB Time limit exceeded

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2091 ms 291352 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 856 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 2 ms 844 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 245 ms 51904 KB Output is correct
10 Correct 297 ms 64308 KB Output is correct
11 Correct 283 ms 62964 KB Output is correct
12 Correct 305 ms 66760 KB Output is correct
13 Correct 321 ms 67984 KB Output is correct
14 Correct 232 ms 51520 KB Output is correct
15 Correct 356 ms 66356 KB Output is correct
16 Correct 330 ms 63604 KB Output is correct
17 Correct 375 ms 69804 KB Output is correct
18 Correct 366 ms 68780 KB Output is correct
19 Incorrect 175 ms 62284 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 2091 ms 291352 KB Time limit exceeded