oj.uz

답안 #560255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
560255 2022-05-11T08:12:56 Z HappyPacMan 자매 도시 (APIO20_swap) C++14
13 / 100
 257 ms 37684 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 4;
vector<int> sack[maxn];
vector<pair<int,int> > ucond[maxn];
int dsu[maxn],uturn[maxn],adjs[maxn];

void join(int u,int v,int w){
    if(dsu[u] != dsu[v]){
        if(sack[dsu[v]].size() > sack[dsu[u]].size()){
            swap(u,v);
        }
        for(int it : sack[dsu[v]]){
            sack[dsu[u]].emplace_back(it);
            dsu[it] = dsu[u];
            ucond[it].emplace_back(dsu[it],w);
        }
    }else if(uturn[dsu[u]] == -1){
        uturn[dsu[u]] = w;
    }
    adjs[u]++;
    adjs[v]++;
    if((adjs[u] > 2 || adjs[v] > 2) && uturn[dsu[u]] == -1){
        uturn[dsu[u]] = w;
    }
}

void init(int N,int M,vector<int> U,vector<int> V,vector<int> W){
    vector<tuple<int,int,int> > edge;
    for(int i=0;i<N;i++){
        dsu[i] = i;
        uturn[i] = -1;
        sack[i].emplace_back(i);
        ucond[i].emplace_back(i,0);
    }
    for(int i=0;i<M;i++){
        edge.emplace_back(W[i],U[i],V[i]);
    }
    sort(edge.begin(),edge.end());
    for(auto [w,u,v] : edge){
        join(u,v,w);
    }
    for(int i=0;i<N;i++){
        reverse(ucond[i].begin(),ucond[i].end());
    }
}

int getMinimumFuelCapacity(int X,int Y){
    int msize = min(ucond[X].size(),ucond[Y].size()), best = -1;
    for(int i=0;i<msize;i++){
        if(ucond[X][i].first == ucond[Y][i].first && uturn[ucond[X][i].first] != -1){
            if(best == -1){
                best = max({ucond[X][i].second,ucond[Y][i].second,uturn[ucond[X][i].first]});
            }else{
                best = min(best,max({ucond[X][i].second,ucond[Y][i].second,uturn[ucond[X][i].first]}));
            }
        }
    }
    return best;
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto [w,u,v] : edge){
      |              ^

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9700 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9832 KB Output is correct
6 Correct 6 ms 9840 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 9872 KB Output is correct
9 Correct 117 ms 28384 KB Output is correct
10 Correct 150 ms 32256 KB Output is correct
11 Correct 153 ms 31824 KB Output is correct
12 Correct 163 ms 33152 KB Output is correct
13 Correct 101 ms 25688 KB Output is correct
14 Correct 125 ms 28636 KB Output is correct
15 Correct 227 ms 36544 KB Output is correct
16 Correct 212 ms 35784 KB Output is correct
17 Correct 229 ms 37336 KB Output is correct
18 Correct 165 ms 29564 KB Output is correct
19 Correct 67 ms 18160 KB Output is correct
20 Correct 226 ms 36648 KB Output is correct
21 Correct 212 ms 36364 KB Output is correct
22 Correct 257 ms 37684 KB Output is correct
23 Correct 162 ms 29992 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9700 KB Output is correct
3 Correct 138 ms 26596 KB Output is correct
4 Correct 145 ms 26956 KB Output is correct
5 Correct 148 ms 27104 KB Output is correct
6 Correct 140 ms 27044 KB Output is correct
7 Correct 141 ms 27208 KB Output is correct
8 Correct 136 ms 26616 KB Output is correct
9 Correct 141 ms 26988 KB Output is correct
10 Correct 139 ms 26556 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9700 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9832 KB Output is correct
6 Correct 6 ms 9840 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 9872 KB Output is correct
9 Correct 5 ms 9680 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Incorrect 6 ms 9844 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9700 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9832 KB Output is correct
7 Correct 6 ms 9840 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 6 ms 9872 KB Output is correct
10 Correct 117 ms 28384 KB Output is correct
11 Correct 150 ms 32256 KB Output is correct
12 Correct 153 ms 31824 KB Output is correct
13 Correct 163 ms 33152 KB Output is correct
14 Correct 101 ms 25688 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Incorrect 6 ms 9844 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9700 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9832 KB Output is correct
6 Correct 6 ms 9840 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 9872 KB Output is correct
9 Correct 117 ms 28384 KB Output is correct
10 Correct 150 ms 32256 KB Output is correct
11 Correct 153 ms 31824 KB Output is correct
12 Correct 163 ms 33152 KB Output is correct
13 Correct 101 ms 25688 KB Output is correct
14 Correct 125 ms 28636 KB Output is correct
15 Correct 227 ms 36544 KB Output is correct
16 Correct 212 ms 35784 KB Output is correct
17 Correct 229 ms 37336 KB Output is correct
18 Correct 165 ms 29564 KB Output is correct
19 Correct 138 ms 26596 KB Output is correct
20 Correct 145 ms 26956 KB Output is correct
21 Correct 148 ms 27104 KB Output is correct
22 Correct 140 ms 27044 KB Output is correct
23 Correct 141 ms 27208 KB Output is correct
24 Correct 136 ms 26616 KB Output is correct
25 Correct 141 ms 26988 KB Output is correct
26 Correct 139 ms 26556 KB Output is correct
27 Correct 6 ms 9812 KB Output is correct
28 Incorrect 6 ms 9844 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9700 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9832 KB Output is correct
7 Correct 6 ms 9840 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 6 ms 9872 KB Output is correct
10 Correct 117 ms 28384 KB Output is correct
11 Correct 150 ms 32256 KB Output is correct
12 Correct 153 ms 31824 KB Output is correct
13 Correct 163 ms 33152 KB Output is correct
14 Correct 101 ms 25688 KB Output is correct
15 Correct 125 ms 28636 KB Output is correct
16 Correct 227 ms 36544 KB Output is correct
17 Correct 212 ms 35784 KB Output is correct
18 Correct 229 ms 37336 KB Output is correct
19 Correct 165 ms 29564 KB Output is correct
20 Correct 138 ms 26596 KB Output is correct
21 Correct 145 ms 26956 KB Output is correct
22 Correct 148 ms 27104 KB Output is correct
23 Correct 140 ms 27044 KB Output is correct
24 Correct 141 ms 27208 KB Output is correct
25 Correct 136 ms 26616 KB Output is correct
26 Correct 141 ms 26988 KB Output is correct
27 Correct 139 ms 26556 KB Output is correct
28 Correct 6 ms 9812 KB Output is correct
29 Incorrect 6 ms 9844 KB Output isn't correct
30 Halted 0 ms 0 KB -