oj.uz

Submission #308121

# Submission time Handle Problem Language Result Execution time Memory
308121 2020-09-30T04:28:39 Z tjdgus4384 Swapping Cities (APIO20_swap) C++14
7 / 100
 290 ms 19436 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int> group[100010];
vector<pair<int, int> > pa[100010];
vector<pair<int, pair<int, int> > > mv;
int p[100010], cycle[100010], outd[100010], sizep[100010], cnt[100010];

int find(int x){
    if(p[x] == x) return x;
    return find(p[x]);
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
    for(int i = 0;i < n;i++){
        sizep[i] = 1; p[i] = i;
        group[i].push_back(i);
        pa[i].push_back({0, i});
    }
    for(int i = 0;i < m;i++){
        mv.push_back({w[i], {u[i], v[i]}});
    }
    sort(mv.begin(), mv.end());
    /*for(int i = 0;i < m;i++){
        printf("%d %d %d\n", mv[i].first, mv[i].second.first, mv[i].second.second);
    }*/
    for(int i = 0;i < m;i++){
        int u1 = find(mv[i].second.first);
        int u2 = find(mv[i].second.second);
        cnt[mv[i].second.first]++; cnt[mv[i].second.second]++;
        if(u1 == u2){
            if(cycle[u1] == 0) cycle[u1] = mv[i].first;
            if(cnt[mv[i].second.first] >= 3 || cnt[mv[i].second.second] >= 3){
                if(outd[u1] == 0) outd[u1] = mv[i].first;
            }
        }
        else{
            if(sizep[u1] < sizep[u2]) swap(u1, u2);
            for(int j = 0;j < group[u2].size();j++){
                pa[group[u2][j]].push_back({mv[i].first, u1});
                p[group[u2][j]] = u1;
            }
            sizep[u1] += sizep[u2];
            if(cycle[u1] || cycle[u2]){
                if(cycle[u2] == 0) cycle[u2] = mv[i].first;
                if(cycle[u1] == 0) cycle[u1] = mv[i].first;
            }
            if(outd[u1] || outd[u2] || cnt[mv[i].second.first] >= 3 || cnt[mv[i].second.second] >= 3){
                if(outd[u1] == 0) outd[u1] = mv[i].first;
                if(outd[u2] == 0) outd[u2] = mv[i].first;
            }
        }
    }
}

int getMinimumFuelCapacity(int X, int Y){
    int x = X, y = Y, ans = 1000000001;
    int s1 = 0, e1 = pa[x].size() - 1;
    while(s1 < e1){
        int mid = (s1+e1)/2;
        if(cycle[pa[x][mid].second]||outd[pa[x][mid].second]) e1 = mid;
        else s1 = mid+1;
    }
    int s2 = 0, e2 = pa[y].size() - 1;
    while(s2 < e2){
        int mid = (s2+e2)/2;
        if(cycle[pa[y][mid].second]||outd[pa[y][mid].second]) e2 = mid;
        else s2 = mid+1;
    }
    if(cycle[pa[x][s1].second]) ans = min(ans, cycle[pa[x][s1].second]);
    if(outd[pa[y][s2].second]) ans = min(ans, outd[pa[y][s2].second]);
    if(outd[pa[x][s1].second]) ans = min(ans, outd[pa[x][s1].second]);
    if(cycle[pa[y][s2].second]) ans = min(ans, cycle[pa[y][s2].second]);
    if(ans == 1000000001) return -1;
    int s = 0, e = 1000000001;
    while(s < e){
        //printf("%d %d\n", s, e);
        int mid = (s+e)/2;
        s1 = 0, e1 = pa[x].size() - 1;
        while(s1 < e1){
            int mid1 = (s1+e1+1)/2;
            if(pa[x][mid1].first > mid) e1 = mid1-1;
            else s1 = mid1;
        }
        s2 = 0, e2 = pa[y].size() - 1;
        while(s2 < e2){
            int mid2 = (s2+e2+1)/2;
            if(pa[y][mid2].first > mid) e2 = mid2-1;
            else s2 = mid2;
        }
        if(pa[x][s1].second != pa[y][s2].second) s = mid+1;
        else e = mid;
    }
    return max(ans, s);
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:38:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             for(int j = 0;j < group[u2].size();j++){
      |                           ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5096 KB Output is correct
7 Correct 4 ms 5120 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 91 ms 14068 KB Output is correct
10 Correct 111 ms 15668 KB Output is correct
11 Correct 112 ms 15600 KB Output is correct
12 Correct 118 ms 16112 KB Output is correct
13 Correct 122 ms 16112 KB Output is correct
14 Correct 98 ms 14192 KB Output is correct
15 Correct 223 ms 17784 KB Output is correct
16 Correct 205 ms 17308 KB Output is correct
17 Correct 215 ms 18004 KB Output is correct
18 Correct 212 ms 17876 KB Output is correct
19 Incorrect 81 ms 9272 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 288 ms 18832 KB Output is correct
4 Correct 284 ms 19280 KB Output is correct
5 Correct 289 ms 19332 KB Output is correct
6 Correct 277 ms 19156 KB Output is correct
7 Correct 290 ms 19436 KB Output is correct
8 Correct 285 ms 18824 KB Output is correct
9 Correct 287 ms 19052 KB Output is correct
10 Correct 281 ms 18772 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5024 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 5120 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 4 ms 5096 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 4 ms 5120 KB Output is correct
10 Incorrect 4 ms 5120 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5024 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 5120 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 4 ms 5096 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 4 ms 5120 KB Output is correct
10 Correct 91 ms 14068 KB Output is correct
11 Correct 111 ms 15668 KB Output is correct
12 Correct 112 ms 15600 KB Output is correct
13 Correct 118 ms 16112 KB Output is correct
14 Correct 122 ms 16112 KB Output is correct
15 Incorrect 4 ms 5120 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5096 KB Output is correct
7 Correct 4 ms 5120 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 91 ms 14068 KB Output is correct
10 Correct 111 ms 15668 KB Output is correct
11 Correct 112 ms 15600 KB Output is correct
12 Correct 118 ms 16112 KB Output is correct
13 Correct 122 ms 16112 KB Output is correct
14 Correct 98 ms 14192 KB Output is correct
15 Correct 223 ms 17784 KB Output is correct
16 Correct 205 ms 17308 KB Output is correct
17 Correct 215 ms 18004 KB Output is correct
18 Correct 212 ms 17876 KB Output is correct
19 Correct 288 ms 18832 KB Output is correct
20 Correct 284 ms 19280 KB Output is correct
21 Correct 289 ms 19332 KB Output is correct
22 Correct 277 ms 19156 KB Output is correct
23 Correct 290 ms 19436 KB Output is correct
24 Correct 285 ms 18824 KB Output is correct
25 Correct 287 ms 19052 KB Output is correct
26 Correct 281 ms 18772 KB Output is correct
27 Incorrect 4 ms 5120 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5024 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 5120 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 4 ms 5096 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 4 ms 5120 KB Output is correct
10 Correct 91 ms 14068 KB Output is correct
11 Correct 111 ms 15668 KB Output is correct
12 Correct 112 ms 15600 KB Output is correct
13 Correct 118 ms 16112 KB Output is correct
14 Correct 122 ms 16112 KB Output is correct
15 Correct 98 ms 14192 KB Output is correct
16 Correct 223 ms 17784 KB Output is correct
17 Correct 205 ms 17308 KB Output is correct
18 Correct 215 ms 18004 KB Output is correct
19 Correct 212 ms 17876 KB Output is correct
20 Correct 288 ms 18832 KB Output is correct
21 Correct 284 ms 19280 KB Output is correct
22 Correct 289 ms 19332 KB Output is correct
23 Correct 277 ms 19156 KB Output is correct
24 Correct 290 ms 19436 KB Output is correct
25 Correct 285 ms 18824 KB Output is correct
26 Correct 287 ms 19052 KB Output is correct
27 Correct 281 ms 18772 KB Output is correct
28 Incorrect 4 ms 5120 KB Output isn't correct
29 Halted 0 ms 0 KB -