oj.uz

Submission #683016

# Submission time Handle Problem Language Result Execution time Memory
683016 2023-01-17T14:25:02 Z Nursik Swapping Cities (APIO20_swap) C++14
13 / 100
 2000 ms 64528 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;
    if (cycle)
        return;
    for (auto to : g2[v]){
        int nx = to;
        if (nx != p){
            if (used[nx] == 0){
                dfs(nx, v);
            }
            else{
                cycle = 1;
                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 22 ms 47168 KB Output is correct
2 Correct 25 ms 47280 KB Output is correct
3 Correct 25 ms 47200 KB Output is correct
4 Correct 23 ms 47292 KB Output is correct
5 Correct 27 ms 47276 KB Output is correct
6 Correct 24 ms 47356 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct
8 Correct 23 ms 47352 KB Output is correct
9 Correct 81 ms 56316 KB Output is correct
10 Correct 98 ms 58060 KB Output is correct
11 Correct 96 ms 57984 KB Output is correct
12 Correct 107 ms 58744 KB Output is correct
13 Correct 107 ms 58588 KB Output is correct
14 Correct 85 ms 56316 KB Output is correct
15 Correct 141 ms 60000 KB Output is correct
16 Correct 146 ms 59768 KB Output is correct
17 Correct 150 ms 60388 KB Output is correct
18 Correct 153 ms 60352 KB Output is correct
19 Correct 82 ms 52572 KB Output is correct
20 Correct 142 ms 61220 KB Output is correct
21 Correct 142 ms 61028 KB Output is correct
22 Correct 151 ms 61792 KB Output is correct
23 Correct 166 ms 61836 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47168 KB Output is correct
2 Correct 25 ms 47280 KB Output is correct
3 Correct 302 ms 61876 KB Output is correct
4 Correct 311 ms 62304 KB Output is correct
5 Correct 344 ms 62144 KB Output is correct
6 Correct 305 ms 62172 KB Output is correct
7 Correct 327 ms 62228 KB Output is correct
8 Correct 316 ms 61732 KB Output is correct
9 Correct 320 ms 62016 KB Output is correct
10 Correct 387 ms 61664 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47168 KB Output is correct
2 Correct 25 ms 47280 KB Output is correct
3 Correct 25 ms 47200 KB Output is correct
4 Correct 23 ms 47292 KB Output is correct
5 Correct 27 ms 47276 KB Output is correct
6 Correct 24 ms 47356 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct
8 Correct 23 ms 47352 KB Output is correct
9 Correct 29 ms 47316 KB Output is correct
10 Correct 24 ms 47316 KB Output is correct
11 Correct 25 ms 47364 KB Output is correct
12 Correct 23 ms 47380 KB Output is correct
13 Correct 24 ms 47316 KB Output is correct
14 Correct 24 ms 47384 KB Output is correct
15 Correct 25 ms 47436 KB Output is correct
16 Correct 24 ms 47392 KB Output is correct
17 Correct 29 ms 47452 KB Output is correct
18 Correct 24 ms 47368 KB Output is correct
19 Incorrect 24 ms 47412 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47316 KB Output is correct
2 Correct 22 ms 47168 KB Output is correct
3 Correct 25 ms 47280 KB Output is correct
4 Correct 25 ms 47200 KB Output is correct
5 Correct 23 ms 47292 KB Output is correct
6 Correct 27 ms 47276 KB Output is correct
7 Correct 24 ms 47356 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 23 ms 47352 KB Output is correct
10 Correct 81 ms 56316 KB Output is correct
11 Correct 98 ms 58060 KB Output is correct
12 Correct 96 ms 57984 KB Output is correct
13 Correct 107 ms 58744 KB Output is correct
14 Correct 107 ms 58588 KB Output is correct
15 Correct 24 ms 47316 KB Output is correct
16 Correct 25 ms 47364 KB Output is correct
17 Correct 23 ms 47380 KB Output is correct
18 Correct 24 ms 47316 KB Output is correct
19 Correct 24 ms 47384 KB Output is correct
20 Correct 25 ms 47436 KB Output is correct
21 Correct 24 ms 47392 KB Output is correct
22 Correct 29 ms 47452 KB Output is correct
23 Correct 24 ms 47368 KB Output is correct
24 Incorrect 24 ms 47412 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47168 KB Output is correct
2 Correct 25 ms 47280 KB Output is correct
3 Correct 25 ms 47200 KB Output is correct
4 Correct 23 ms 47292 KB Output is correct
5 Correct 27 ms 47276 KB Output is correct
6 Correct 24 ms 47356 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct
8 Correct 23 ms 47352 KB Output is correct
9 Correct 81 ms 56316 KB Output is correct
10 Correct 98 ms 58060 KB Output is correct
11 Correct 96 ms 57984 KB Output is correct
12 Correct 107 ms 58744 KB Output is correct
13 Correct 107 ms 58588 KB Output is correct
14 Correct 85 ms 56316 KB Output is correct
15 Correct 141 ms 60000 KB Output is correct
16 Correct 146 ms 59768 KB Output is correct
17 Correct 150 ms 60388 KB Output is correct
18 Correct 153 ms 60352 KB Output is correct
19 Correct 302 ms 61876 KB Output is correct
20 Correct 311 ms 62304 KB Output is correct
21 Correct 344 ms 62144 KB Output is correct
22 Correct 305 ms 62172 KB Output is correct
23 Correct 327 ms 62228 KB Output is correct
24 Correct 316 ms 61732 KB Output is correct
25 Correct 320 ms 62016 KB Output is correct
26 Correct 387 ms 61664 KB Output is correct
27 Correct 24 ms 47316 KB Output is correct
28 Correct 25 ms 47364 KB Output is correct
29 Correct 23 ms 47380 KB Output is correct
30 Correct 24 ms 47316 KB Output is correct
31 Correct 24 ms 47384 KB Output is correct
32 Correct 25 ms 47436 KB Output is correct
33 Correct 24 ms 47392 KB Output is correct
34 Correct 29 ms 47452 KB Output is correct
35 Correct 24 ms 47368 KB Output is correct
36 Correct 84 ms 49228 KB Output is correct
37 Execution timed out 2082 ms 64528 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47316 KB Output is correct
2 Correct 22 ms 47168 KB Output is correct
3 Correct 25 ms 47280 KB Output is correct
4 Correct 25 ms 47200 KB Output is correct
5 Correct 23 ms 47292 KB Output is correct
6 Correct 27 ms 47276 KB Output is correct
7 Correct 24 ms 47356 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 23 ms 47352 KB Output is correct
10 Correct 81 ms 56316 KB Output is correct
11 Correct 98 ms 58060 KB Output is correct
12 Correct 96 ms 57984 KB Output is correct
13 Correct 107 ms 58744 KB Output is correct
14 Correct 107 ms 58588 KB Output is correct
15 Correct 85 ms 56316 KB Output is correct
16 Correct 141 ms 60000 KB Output is correct
17 Correct 146 ms 59768 KB Output is correct
18 Correct 150 ms 60388 KB Output is correct
19 Correct 153 ms 60352 KB Output is correct
20 Correct 302 ms 61876 KB Output is correct
21 Correct 311 ms 62304 KB Output is correct
22 Correct 344 ms 62144 KB Output is correct
23 Correct 305 ms 62172 KB Output is correct
24 Correct 327 ms 62228 KB Output is correct
25 Correct 316 ms 61732 KB Output is correct
26 Correct 320 ms 62016 KB Output is correct
27 Correct 387 ms 61664 KB Output is correct
28 Correct 24 ms 47316 KB Output is correct
29 Correct 25 ms 47364 KB Output is correct
30 Correct 23 ms 47380 KB Output is correct
31 Correct 24 ms 47316 KB Output is correct
32 Correct 24 ms 47384 KB Output is correct
33 Correct 25 ms 47436 KB Output is correct
34 Correct 24 ms 47392 KB Output is correct
35 Correct 29 ms 47452 KB Output is correct
36 Correct 24 ms 47368 KB Output is correct
37 Correct 84 ms 49228 KB Output is correct
38 Execution timed out 2082 ms 64528 KB Time limit exceeded
39 Halted 0 ms 0 KB -