oj.uz

Submission #385173

# Submission time Handle Problem Language Result Execution time Memory
385173 2021-04-03T12:51:13 Z kwongweng Swapping Cities (APIO20_swap) C++17
6 / 100
 118 ms 13944 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define F first
#define S second

int l = 0;
vector<pair<int, ii>> edges;
vi p, r, deg, maxi, num, sz;
void init(int n, int m, vi U, vi V, vi W) {
    FOR(i, 0, m){
        edges.pb({W[i], {U[i], V[i]}});
        l = max(l, W[i]);
    }
    if (m == n-1) l = -1;
    sort(edges.begin(), edges.end());
    p.resize(n);
    r.resize(n);
    deg.resize(n);
    maxi.resize(n);
    num.resize(n);
    sz.resize(n);
}

int get(int a){
    return p[a] = (p[a] == a ? a : get(p[a]));
}

void Union(int c, int d){
    int a = get(c), b = get(d);
    if (a == b) return;
    if (r[a] == r[b]) r[a]++;
    if (r[a] > r[b]){
        p[b] = a;
        maxi[a] = max(maxi[b], maxi[a]);
        num[a] += num[b];
        sz[a] += sz[b];
    }else{
        p[a] = b;
        maxi[b] = max(maxi[a], maxi[b]);
        num[b] += num[a];
        sz[b] += sz[a];
    }
}


int getMinimumFuelCapacity(int x, int y) {
    return l;
    FOR(i, 0, p.size()) p[i] = i;
    FOR(i, 0, r.size()){
        r[i] = 0; deg[i] = 0, maxi[i] = 0; num[i] = 0; sz[i] = 1;
    }
    FOR(i, 0, edges.size()){
        int a = edges[i].S.F, b = edges[i].S.S;
        Union(a, b);
        deg[a]++; deg[b]++;
        maxi[get(a)] = max(maxi[get(a)], deg[a]);
        maxi[get(b)] = max(maxi[get(b)], deg[b]);
        num[get(a)]++;
        if (get(x) != get(y)) continue;
        if (maxi[get(x)] < 3 && num[get(x)] < sz[get(x)]) continue;
        return edges[i].F;
    }
    return -1;
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:8:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
   57 |     FOR(i, 0, p.size()) p[i] = i;
      |         ~~~~~~~~~~~~~~                 
swap.cpp:57:5: note: in expansion of macro 'FOR'
   57 |     FOR(i, 0, p.size()) p[i] = i;
      |     ^~~
swap.cpp:8:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
   58 |     FOR(i, 0, r.size()){
      |         ~~~~~~~~~~~~~~                 
swap.cpp:58:5: note: in expansion of macro 'FOR'
   58 |     FOR(i, 0, r.size()){
      |     ^~~
swap.cpp:8:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
   61 |     FOR(i, 0, edges.size()){
      |         ~~~~~~~~~~~~~~~~~~             
swap.cpp:61:5: note: in expansion of macro 'FOR'
   61 |     FOR(i, 0, edges.size()){
      |     ^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 38 ms 4960 KB Output is correct
10 Correct 49 ms 5984 KB Output is correct
11 Correct 45 ms 5856 KB Output is correct
12 Correct 47 ms 6240 KB Output is correct
13 Correct 49 ms 6240 KB Output is correct
14 Correct 44 ms 5088 KB Output is correct
15 Correct 113 ms 12392 KB Output is correct
16 Correct 110 ms 11920 KB Output is correct
17 Correct 115 ms 12356 KB Output is correct
18 Correct 117 ms 12356 KB Output is correct
19 Correct 63 ms 6828 KB Output is correct
20 Correct 111 ms 13148 KB Output is correct
21 Correct 118 ms 13336 KB Output is correct
22 Correct 117 ms 13764 KB Output is correct
23 Correct 117 ms 13944 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 104 ms 7556 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Incorrect 1 ms 512 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 38 ms 4960 KB Output is correct
10 Correct 49 ms 5984 KB Output is correct
11 Correct 45 ms 5856 KB Output is correct
12 Correct 47 ms 6240 KB Output is correct
13 Correct 49 ms 6240 KB Output is correct
14 Correct 44 ms 5088 KB Output is correct
15 Correct 113 ms 12392 KB Output is correct
16 Correct 110 ms 11920 KB Output is correct
17 Correct 115 ms 12356 KB Output is correct
18 Correct 117 ms 12356 KB Output is correct
19 Incorrect 104 ms 7556 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct