oj.uz

Submission #308122

# Submission time Handle Problem Language Result Execution time Memory
308122 2020-09-30T04:29:40 Z tjdgus4384 Swapping Cities (APIO20_swap) C++14
7 / 100
 302 ms 19340 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;
    }
    if(e == 1000000001) return -1;
    else 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 4 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 5120 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 14060 KB Output is correct
10 Correct 115 ms 15728 KB Output is correct
11 Correct 114 ms 15604 KB Output is correct
12 Correct 120 ms 16236 KB Output is correct
13 Correct 120 ms 16112 KB Output is correct
14 Correct 98 ms 14192 KB Output is correct
15 Correct 214 ms 17528 KB Output is correct
16 Correct 206 ms 17248 KB Output is correct
17 Correct 222 ms 17876 KB Output is correct
18 Correct 218 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 282 ms 18840 KB Output is correct
4 Correct 281 ms 19188 KB Output is correct
5 Correct 302 ms 19340 KB Output is correct
6 Correct 277 ms 19160 KB Output is correct
7 Correct 290 ms 19308 KB Output is correct
8 Correct 291 ms 18916 KB Output is correct
9 Correct 282 ms 19180 KB Output is correct
10 Correct 278 ms 18728 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 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 5120 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 4 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 4 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 5120 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 14060 KB Output is correct
11 Correct 115 ms 15728 KB Output is correct
12 Correct 114 ms 15604 KB Output is correct
13 Correct 120 ms 16236 KB Output is correct
14 Correct 120 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 4 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 5120 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 14060 KB Output is correct
10 Correct 115 ms 15728 KB Output is correct
11 Correct 114 ms 15604 KB Output is correct
12 Correct 120 ms 16236 KB Output is correct
13 Correct 120 ms 16112 KB Output is correct
14 Correct 98 ms 14192 KB Output is correct
15 Correct 214 ms 17528 KB Output is correct
16 Correct 206 ms 17248 KB Output is correct
17 Correct 222 ms 17876 KB Output is correct
18 Correct 218 ms 17876 KB Output is correct
19 Correct 282 ms 18840 KB Output is correct
20 Correct 281 ms 19188 KB Output is correct
21 Correct 302 ms 19340 KB Output is correct
22 Correct 277 ms 19160 KB Output is correct
23 Correct 290 ms 19308 KB Output is correct
24 Correct 291 ms 18916 KB Output is correct
25 Correct 282 ms 19180 KB Output is correct
26 Correct 278 ms 18728 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 4 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 4 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 5120 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 14060 KB Output is correct
11 Correct 115 ms 15728 KB Output is correct
12 Correct 114 ms 15604 KB Output is correct
13 Correct 120 ms 16236 KB Output is correct
14 Correct 120 ms 16112 KB Output is correct
15 Correct 98 ms 14192 KB Output is correct
16 Correct 214 ms 17528 KB Output is correct
17 Correct 206 ms 17248 KB Output is correct
18 Correct 222 ms 17876 KB Output is correct
19 Correct 218 ms 17876 KB Output is correct
20 Correct 282 ms 18840 KB Output is correct
21 Correct 281 ms 19188 KB Output is correct
22 Correct 302 ms 19340 KB Output is correct
23 Correct 277 ms 19160 KB Output is correct
24 Correct 290 ms 19308 KB Output is correct
25 Correct 291 ms 18916 KB Output is correct
26 Correct 282 ms 19180 KB Output is correct
27 Correct 278 ms 18728 KB Output is correct
28 Incorrect 4 ms 5120 KB Output isn't correct
29 Halted 0 ms 0 KB -