oj.uz

답안 #409879

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409879 2021-05-21T17:52:51 Z Ahmad_Hasan 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 452696 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<20;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<20;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<20;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>(20,-1));
    mn=vector<vector<int> >(n,vector<int>(20,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: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

# 결과 실행 시간 메모리 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 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 202 ms 41028 KB Output is correct
10 Correct 262 ms 50704 KB Output is correct
11 Correct 255 ms 49656 KB Output is correct
12 Correct 274 ms 52672 KB Output is correct
13 Correct 287 ms 53768 KB Output is correct
14 Correct 206 ms 40516 KB Output is correct
15 Correct 337 ms 52768 KB Output is correct
16 Correct 337 ms 50468 KB Output is correct
17 Correct 369 ms 55548 KB Output is correct
18 Correct 346 ms 54684 KB Output is correct
19 Execution timed out 2083 ms 88792 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 177 ms 49060 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 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 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Execution timed out 2111 ms 452696 KB Time limit exceeded

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2111 ms 452696 KB Time limit exceeded

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 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 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 202 ms 41028 KB Output is correct
10 Correct 262 ms 50704 KB Output is correct
11 Correct 255 ms 49656 KB Output is correct
12 Correct 274 ms 52672 KB Output is correct
13 Correct 287 ms 53768 KB Output is correct
14 Correct 206 ms 40516 KB Output is correct
15 Correct 337 ms 52768 KB Output is correct
16 Correct 337 ms 50468 KB Output is correct
17 Correct 369 ms 55548 KB Output is correct
18 Correct 346 ms 54684 KB Output is correct
19 Incorrect 177 ms 49060 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2111 ms 452696 KB Time limit exceeded