oj.uz

Submission #683015

# Submission time Handle Problem Language Result Execution time Memory
683015 2023-01-17T14:22:28 Z Nursik Swapping Cities (APIO20_swap) C++14
13 / 100
 2000 ms 64436 KB 
#include "swap.h"

#include <stdio.h>
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define mp make_pair
#define f first
#define s second
#define pb push_back

const int maxn = 1e6 + 200;

int subtask2 = 1, subtask1 = 1, cycle = 0;
int used[maxn];
multiset<int> setik;
vector<pair<int, int>> g[maxn];
vector<int> g2[maxn];
int ver, reb;
vector<pair<int, pair<int, int>>> kektor;
void dfs(int v, int p){
    used[v] = 1;
    for (auto to : g2[v]){
        int nx = to;
        if (nx != p){
            if (used[nx] == 0){
                dfs(nx, v);
            }
            else{
                cycle = 1;
              //  cout << v << " " << to << '\n';
                return;
            }
        }
    }
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    for (int i = 0; i < m; ++i){
        int x = u[i], y = v[i];
        g[x].pb(mp(y, w[i]));
        g[y].pb(mp(x, w[i]));
        kektor.pb(mp(w[i], mp(x, y)));
    }
    for (auto it : u){
        subtask2 &= (it == 0);
    }
    subtask2 &= (m == n - 1);
    for (auto it : w){
        setik.insert(it);
    }
    for (int i = 1; i <= n; ++i){
        int sz = (int)g[i].size();
        subtask1 &= (sz <= 2);
    }
    ver = n, reb = m;
    sort(kektor.begin(), kektor.end());
}
int getMinimumFuelCapacity(int x, int y) {
    if (subtask2 == 1){
        if (x == 0){
            int cur = g[y][0].s;
            setik.erase(setik.find(cur));
            int sz = (int)setik.size();
            if (sz == 0){
                setik.insert(cur);
                return -1;
            }
            sz -= 1;
            int cur2 = *setik.begin();
            setik.erase(setik.find(cur2));
            if (sz == 0){
                setik.insert(cur);
                setik.insert(cur2);
                return -1;
            }    
            sz -= 1;
            int cur3 = *setik.begin();
            setik.insert(cur);
            setik.insert(cur2);
            return max({cur, cur2, cur3});
        }
        int cur = g[x][0].s;
        int cur2 = g[y][0].s;
        setik.erase(setik.find(cur));
        setik.erase(setik.find(cur2));
        if ((int)setik.size() == 0){
            setik.insert(cur);
            setik.insert(cur2);
            return -1;
        }
        int cur3 = *setik.begin();
        setik.insert(cur);
        setik.insert(cur2);
        return max({cur, cur2, cur3});
    }
    if (subtask1 == 1){
        if (reb == ver - 1){
            return -1;
        }
        else{
            return *setik.rbegin();
        }
    }
    for (int i = 0; i < ver; ++i){
        g2[i].clear();
    }
    for (int i = 0; i < reb; ++i){
        pair<int, pair<int, int>> cur = kektor[i];
        int xu = cur.s.f, yu = cur.s.s;
        g2[xu].pb(yu);
        g2[yu].pb(xu);
        cycle = 0;
        for (int j = 0; j < ver; ++j){
            used[j] = 0;
        }
        dfs(x, -1);
        if (cycle && used[y]){
            return cur.f;
        }
        if (used[y] > 0){
            for (int j = 0; j < ver; ++j){
                int sz = (int)g2[j].size();
                if (sz >= 3 && used[j] > 0){
                    return cur.f;
                }
            }
        }
    }
    return -1;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 28 ms 47204 KB Output is correct
3 Correct 23 ms 47188 KB Output is correct
4 Correct 25 ms 47316 KB Output is correct
5 Correct 23 ms 47296 KB Output is correct
6 Correct 23 ms 47316 KB Output is correct
7 Correct 24 ms 47392 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 84 ms 56072 KB Output is correct
10 Correct 99 ms 58180 KB Output is correct
11 Correct 109 ms 57924 KB Output is correct
12 Correct 96 ms 58636 KB Output is correct
13 Correct 110 ms 58676 KB Output is correct
14 Correct 94 ms 56308 KB Output is correct
15 Correct 159 ms 60024 KB Output is correct
16 Correct 138 ms 59764 KB Output is correct
17 Correct 148 ms 60520 KB Output is correct
18 Correct 172 ms 60400 KB Output is correct
19 Correct 72 ms 52436 KB Output is correct
20 Correct 142 ms 61196 KB Output is correct
21 Correct 194 ms 61020 KB Output is correct
22 Correct 148 ms 61796 KB Output is correct
23 Correct 146 ms 61764 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 28 ms 47204 KB Output is correct
3 Correct 366 ms 61684 KB Output is correct
4 Correct 334 ms 62184 KB Output is correct
5 Correct 327 ms 62160 KB Output is correct
6 Correct 306 ms 62116 KB Output is correct
7 Correct 380 ms 62216 KB Output is correct
8 Correct 313 ms 61736 KB Output is correct
9 Correct 347 ms 62032 KB Output is correct
10 Correct 297 ms 61648 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 28 ms 47204 KB Output is correct
3 Correct 23 ms 47188 KB Output is correct
4 Correct 25 ms 47316 KB Output is correct
5 Correct 23 ms 47296 KB Output is correct
6 Correct 23 ms 47316 KB Output is correct
7 Correct 24 ms 47392 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 23 ms 47188 KB Output is correct
10 Correct 27 ms 47412 KB Output is correct
11 Correct 30 ms 47336 KB Output is correct
12 Correct 24 ms 47316 KB Output is correct
13 Correct 24 ms 47380 KB Output is correct
14 Correct 25 ms 47324 KB Output is correct
15 Correct 24 ms 47436 KB Output is correct
16 Correct 24 ms 47340 KB Output is correct
17 Correct 29 ms 47384 KB Output is correct
18 Correct 25 ms 47416 KB Output is correct
19 Correct 25 ms 47320 KB Output is correct
20 Incorrect 25 ms 47444 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 28 ms 47204 KB Output is correct
4 Correct 23 ms 47188 KB Output is correct
5 Correct 25 ms 47316 KB Output is correct
6 Correct 23 ms 47296 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct
8 Correct 24 ms 47392 KB Output is correct
9 Correct 23 ms 47316 KB Output is correct
10 Correct 84 ms 56072 KB Output is correct
11 Correct 99 ms 58180 KB Output is correct
12 Correct 109 ms 57924 KB Output is correct
13 Correct 96 ms 58636 KB Output is correct
14 Correct 110 ms 58676 KB Output is correct
15 Correct 27 ms 47412 KB Output is correct
16 Correct 30 ms 47336 KB Output is correct
17 Correct 24 ms 47316 KB Output is correct
18 Correct 24 ms 47380 KB Output is correct
19 Correct 25 ms 47324 KB Output is correct
20 Correct 24 ms 47436 KB Output is correct
21 Correct 24 ms 47340 KB Output is correct
22 Correct 29 ms 47384 KB Output is correct
23 Correct 25 ms 47416 KB Output is correct
24 Correct 25 ms 47320 KB Output is correct
25 Incorrect 25 ms 47444 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 28 ms 47204 KB Output is correct
3 Correct 23 ms 47188 KB Output is correct
4 Correct 25 ms 47316 KB Output is correct
5 Correct 23 ms 47296 KB Output is correct
6 Correct 23 ms 47316 KB Output is correct
7 Correct 24 ms 47392 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 84 ms 56072 KB Output is correct
10 Correct 99 ms 58180 KB Output is correct
11 Correct 109 ms 57924 KB Output is correct
12 Correct 96 ms 58636 KB Output is correct
13 Correct 110 ms 58676 KB Output is correct
14 Correct 94 ms 56308 KB Output is correct
15 Correct 159 ms 60024 KB Output is correct
16 Correct 138 ms 59764 KB Output is correct
17 Correct 148 ms 60520 KB Output is correct
18 Correct 172 ms 60400 KB Output is correct
19 Correct 366 ms 61684 KB Output is correct
20 Correct 334 ms 62184 KB Output is correct
21 Correct 327 ms 62160 KB Output is correct
22 Correct 306 ms 62116 KB Output is correct
23 Correct 380 ms 62216 KB Output is correct
24 Correct 313 ms 61736 KB Output is correct
25 Correct 347 ms 62032 KB Output is correct
26 Correct 297 ms 61648 KB Output is correct
27 Correct 27 ms 47412 KB Output is correct
28 Correct 30 ms 47336 KB Output is correct
29 Correct 24 ms 47316 KB Output is correct
30 Correct 24 ms 47380 KB Output is correct
31 Correct 25 ms 47324 KB Output is correct
32 Correct 24 ms 47436 KB Output is correct
33 Correct 24 ms 47340 KB Output is correct
34 Correct 29 ms 47384 KB Output is correct
35 Correct 25 ms 47416 KB Output is correct
36 Correct 83 ms 49104 KB Output is correct
37 Execution timed out 2071 ms 64436 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 28 ms 47204 KB Output is correct
4 Correct 23 ms 47188 KB Output is correct
5 Correct 25 ms 47316 KB Output is correct
6 Correct 23 ms 47296 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct
8 Correct 24 ms 47392 KB Output is correct
9 Correct 23 ms 47316 KB Output is correct
10 Correct 84 ms 56072 KB Output is correct
11 Correct 99 ms 58180 KB Output is correct
12 Correct 109 ms 57924 KB Output is correct
13 Correct 96 ms 58636 KB Output is correct
14 Correct 110 ms 58676 KB Output is correct
15 Correct 94 ms 56308 KB Output is correct
16 Correct 159 ms 60024 KB Output is correct
17 Correct 138 ms 59764 KB Output is correct
18 Correct 148 ms 60520 KB Output is correct
19 Correct 172 ms 60400 KB Output is correct
20 Correct 366 ms 61684 KB Output is correct
21 Correct 334 ms 62184 KB Output is correct
22 Correct 327 ms 62160 KB Output is correct
23 Correct 306 ms 62116 KB Output is correct
24 Correct 380 ms 62216 KB Output is correct
25 Correct 313 ms 61736 KB Output is correct
26 Correct 347 ms 62032 KB Output is correct
27 Correct 297 ms 61648 KB Output is correct
28 Correct 27 ms 47412 KB Output is correct
29 Correct 30 ms 47336 KB Output is correct
30 Correct 24 ms 47316 KB Output is correct
31 Correct 24 ms 47380 KB Output is correct
32 Correct 25 ms 47324 KB Output is correct
33 Correct 24 ms 47436 KB Output is correct
34 Correct 24 ms 47340 KB Output is correct
35 Correct 29 ms 47384 KB Output is correct
36 Correct 25 ms 47416 KB Output is correct
37 Correct 83 ms 49104 KB Output is correct
38 Execution timed out 2071 ms 64436 KB Time limit exceeded
39 Halted 0 ms 0 KB -