oj.uz

Submission #683029

# Submission time Handle Problem Language Result Execution time Memory
683029 2023-01-17T14:48:07 Z Nursik Swapping Cities (APIO20_swap) C++14
30 / 100
 2000 ms 64836 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;
            }
        }
    }
}
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)));
       // g2[x].pb(y);
       // g2[y].pb(x);
    }
   // dfs(364, -1);
    /*for (int i = 0; i < n; ++i){
        if (used[i] == 0){
            cout << i << '\n';
        }
    }
    cout << used[588];
    exit(0);*/
    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());
    /*for (int i = 0; i < m; ++i){
        int x = kektor[i].s.f, y = kektor[i].s.s;
        g2[x].pb(y);
        g2[y].pb(x);
        for (int j = 0; j < n; ++j){
            used[j] = 0;
        }
        cycle = 0;
        dfs(364, -1);
        if (cycle && used[588]){
           // cout << i << '\n';
            cout << kektor[i].f << '\n';
            exit(0);
        }
        for (int j = 0; j < n; ++j){
            int sz = (int)g2[j].size();
            if (sz >= 3 && used[j] && used[588]){
                cout << kektor[i].f << '\n';
                exit(0);
            }
        }
        if (kektor[i].f == 998840){
            cout << i << '\n';
            cout << "lol\n";
            exit(0);
        }
        if (used[588]){
            cout << i << '\n';
            exit(0);
        }
        if (x == 588 || y == 588){
            cout << "yes\n";
            cout << i << '\n';
            exit(0);
        }
    }*/
}
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 47188 KB Output is correct
2 Correct 24 ms 47208 KB Output is correct
3 Correct 23 ms 47176 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Correct 25 ms 47284 KB Output is correct
6 Correct 24 ms 47300 KB Output is correct
7 Correct 26 ms 47300 KB Output is correct
8 Correct 23 ms 47292 KB Output is correct
9 Correct 96 ms 56320 KB Output is correct
10 Correct 91 ms 58352 KB Output is correct
11 Correct 99 ms 58248 KB Output is correct
12 Correct 103 ms 58880 KB Output is correct
13 Correct 100 ms 58960 KB Output is correct
14 Correct 84 ms 56576 KB Output is correct
15 Correct 153 ms 60384 KB Output is correct
16 Correct 137 ms 59972 KB Output is correct
17 Correct 143 ms 60584 KB Output is correct
18 Correct 147 ms 60648 KB Output is correct
19 Correct 72 ms 52812 KB Output is correct
20 Correct 139 ms 61424 KB Output is correct
21 Correct 143 ms 61368 KB Output is correct
22 Correct 143 ms 62016 KB Output is correct
23 Correct 148 ms 62080 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Correct 24 ms 47208 KB Output is correct
3 Correct 317 ms 62064 KB Output is correct
4 Correct 336 ms 62552 KB Output is correct
5 Correct 380 ms 62348 KB Output is correct
6 Correct 307 ms 62312 KB Output is correct
7 Correct 335 ms 62544 KB Output is correct
8 Correct 309 ms 62012 KB Output is correct
9 Correct 324 ms 62308 KB Output is correct
10 Correct 305 ms 61900 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Correct 24 ms 47208 KB Output is correct
3 Correct 23 ms 47176 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Correct 25 ms 47284 KB Output is correct
6 Correct 24 ms 47300 KB Output is correct
7 Correct 26 ms 47300 KB Output is correct
8 Correct 23 ms 47292 KB Output is correct
9 Correct 23 ms 47212 KB Output is correct
10 Correct 24 ms 47332 KB Output is correct
11 Correct 24 ms 47432 KB Output is correct
12 Correct 24 ms 47444 KB Output is correct
13 Correct 24 ms 47308 KB Output is correct
14 Correct 25 ms 47300 KB Output is correct
15 Correct 24 ms 47444 KB Output is correct
16 Correct 25 ms 47400 KB Output is correct
17 Correct 31 ms 47436 KB Output is correct
18 Correct 26 ms 47420 KB Output is correct
19 Correct 25 ms 47440 KB Output is correct
20 Correct 27 ms 47436 KB Output is correct
21 Correct 25 ms 47416 KB Output is correct
22 Correct 24 ms 47424 KB Output is correct
23 Correct 24 ms 47380 KB Output is correct
24 Correct 25 ms 47428 KB Output is correct
25 Correct 26 ms 47548 KB Output is correct
26 Correct 24 ms 47440 KB Output is correct
27 Correct 32 ms 47420 KB Output is correct
28 Correct 24 ms 47432 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47212 KB Output is correct
2 Correct 22 ms 47188 KB Output is correct
3 Correct 24 ms 47208 KB Output is correct
4 Correct 23 ms 47176 KB Output is correct
5 Correct 23 ms 47316 KB Output is correct
6 Correct 25 ms 47284 KB Output is correct
7 Correct 24 ms 47300 KB Output is correct
8 Correct 26 ms 47300 KB Output is correct
9 Correct 23 ms 47292 KB Output is correct
10 Correct 96 ms 56320 KB Output is correct
11 Correct 91 ms 58352 KB Output is correct
12 Correct 99 ms 58248 KB Output is correct
13 Correct 103 ms 58880 KB Output is correct
14 Correct 100 ms 58960 KB Output is correct
15 Correct 24 ms 47332 KB Output is correct
16 Correct 24 ms 47432 KB Output is correct
17 Correct 24 ms 47444 KB Output is correct
18 Correct 24 ms 47308 KB Output is correct
19 Correct 25 ms 47300 KB Output is correct
20 Correct 24 ms 47444 KB Output is correct
21 Correct 25 ms 47400 KB Output is correct
22 Correct 31 ms 47436 KB Output is correct
23 Correct 26 ms 47420 KB Output is correct
24 Correct 25 ms 47440 KB Output is correct
25 Correct 27 ms 47436 KB Output is correct
26 Correct 25 ms 47416 KB Output is correct
27 Correct 24 ms 47424 KB Output is correct
28 Correct 24 ms 47380 KB Output is correct
29 Correct 25 ms 47428 KB Output is correct
30 Correct 26 ms 47548 KB Output is correct
31 Correct 24 ms 47440 KB Output is correct
32 Correct 32 ms 47420 KB Output is correct
33 Correct 24 ms 47432 KB Output is correct
34 Correct 84 ms 49328 KB Output is correct
35 Execution timed out 2045 ms 64836 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Correct 24 ms 47208 KB Output is correct
3 Correct 23 ms 47176 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Correct 25 ms 47284 KB Output is correct
6 Correct 24 ms 47300 KB Output is correct
7 Correct 26 ms 47300 KB Output is correct
8 Correct 23 ms 47292 KB Output is correct
9 Correct 96 ms 56320 KB Output is correct
10 Correct 91 ms 58352 KB Output is correct
11 Correct 99 ms 58248 KB Output is correct
12 Correct 103 ms 58880 KB Output is correct
13 Correct 100 ms 58960 KB Output is correct
14 Correct 84 ms 56576 KB Output is correct
15 Correct 153 ms 60384 KB Output is correct
16 Correct 137 ms 59972 KB Output is correct
17 Correct 143 ms 60584 KB Output is correct
18 Correct 147 ms 60648 KB Output is correct
19 Correct 317 ms 62064 KB Output is correct
20 Correct 336 ms 62552 KB Output is correct
21 Correct 380 ms 62348 KB Output is correct
22 Correct 307 ms 62312 KB Output is correct
23 Correct 335 ms 62544 KB Output is correct
24 Correct 309 ms 62012 KB Output is correct
25 Correct 324 ms 62308 KB Output is correct
26 Correct 305 ms 61900 KB Output is correct
27 Correct 24 ms 47332 KB Output is correct
28 Correct 24 ms 47432 KB Output is correct
29 Correct 24 ms 47444 KB Output is correct
30 Correct 24 ms 47308 KB Output is correct
31 Correct 25 ms 47300 KB Output is correct
32 Correct 24 ms 47444 KB Output is correct
33 Correct 25 ms 47400 KB Output is correct
34 Correct 31 ms 47436 KB Output is correct
35 Correct 26 ms 47420 KB Output is correct
36 Correct 84 ms 49328 KB Output is correct
37 Execution timed out 2045 ms 64836 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 47212 KB Output is correct
2 Correct 22 ms 47188 KB Output is correct
3 Correct 24 ms 47208 KB Output is correct
4 Correct 23 ms 47176 KB Output is correct
5 Correct 23 ms 47316 KB Output is correct
6 Correct 25 ms 47284 KB Output is correct
7 Correct 24 ms 47300 KB Output is correct
8 Correct 26 ms 47300 KB Output is correct
9 Correct 23 ms 47292 KB Output is correct
10 Correct 96 ms 56320 KB Output is correct
11 Correct 91 ms 58352 KB Output is correct
12 Correct 99 ms 58248 KB Output is correct
13 Correct 103 ms 58880 KB Output is correct
14 Correct 100 ms 58960 KB Output is correct
15 Correct 84 ms 56576 KB Output is correct
16 Correct 153 ms 60384 KB Output is correct
17 Correct 137 ms 59972 KB Output is correct
18 Correct 143 ms 60584 KB Output is correct
19 Correct 147 ms 60648 KB Output is correct
20 Correct 317 ms 62064 KB Output is correct
21 Correct 336 ms 62552 KB Output is correct
22 Correct 380 ms 62348 KB Output is correct
23 Correct 307 ms 62312 KB Output is correct
24 Correct 335 ms 62544 KB Output is correct
25 Correct 309 ms 62012 KB Output is correct
26 Correct 324 ms 62308 KB Output is correct
27 Correct 305 ms 61900 KB Output is correct
28 Correct 24 ms 47332 KB Output is correct
29 Correct 24 ms 47432 KB Output is correct
30 Correct 24 ms 47444 KB Output is correct
31 Correct 24 ms 47308 KB Output is correct
32 Correct 25 ms 47300 KB Output is correct
33 Correct 24 ms 47444 KB Output is correct
34 Correct 25 ms 47400 KB Output is correct
35 Correct 31 ms 47436 KB Output is correct
36 Correct 26 ms 47420 KB Output is correct
37 Correct 84 ms 49328 KB Output is correct
38 Execution timed out 2045 ms 64836 KB Time limit exceeded
39 Halted 0 ms 0 KB -