oj.uz

Submission #682957

# Submission time Handle Problem Language Result Execution time Memory
682957 2023-01-17T11:20:01 Z Nursik Swapping Cities (APIO20_swap) C++14
13 / 100
 2000 ms 66752 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];
int par[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 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);
    }
    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());
}
void dfs(int v, int p){
    used[v] = 1;
    par[v] = p;
    for (auto to : g2[v]){
        int nx = to;
        if (nx != p){
            if (used[nx] == 0){
                dfs(nx, v);
            }
            else{
                cycle = 1;
              /*  cout << to << " " << '\n';
                cout << v << " " << p << '\n';
                cout << "ebat\n";*/
            }
        }
    }
}
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 (auto it : kektor){
        pair<int, pair<int, int>> cur = it;
        int xu = cur.s.f, yu = cur.s.s;
        g2[xu].pb(yu);
        g2[yu].pb(xu);
        cycle = 0;
        for (int i = 0; i < ver; ++i){
            used[i] = 0;
        }
        dfs(x, -1);
        if (cycle){
            return cur.f;
        }
        if (used[y] > 0){
            for (int i = 0; i < ver; ++i){
                int sz = (int)g2[i].size();
                if (sz >= 3 && used[i] > 0){
                    return cur.f;
                }
            }
        }
    }
    return -1;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47340 KB Output is correct
2 Correct 27 ms 47188 KB Output is correct
3 Correct 24 ms 47284 KB Output is correct
4 Correct 25 ms 47316 KB Output is correct
5 Correct 23 ms 47284 KB Output is correct
6 Correct 27 ms 47308 KB Output is correct
7 Correct 26 ms 47316 KB Output is correct
8 Correct 23 ms 47300 KB Output is correct
9 Correct 92 ms 56452 KB Output is correct
10 Correct 99 ms 58676 KB Output is correct
11 Correct 104 ms 58368 KB Output is correct
12 Correct 117 ms 59020 KB Output is correct
13 Correct 98 ms 58904 KB Output is correct
14 Correct 90 ms 56596 KB Output is correct
15 Correct 158 ms 60548 KB Output is correct
16 Correct 170 ms 60180 KB Output is correct
17 Correct 148 ms 60772 KB Output is correct
18 Correct 155 ms 60732 KB Output is correct
19 Correct 82 ms 52860 KB Output is correct
20 Correct 160 ms 61572 KB Output is correct
21 Correct 151 ms 61432 KB Output is correct
22 Correct 162 ms 62204 KB Output is correct
23 Correct 167 ms 62212 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47340 KB Output is correct
2 Correct 27 ms 47188 KB Output is correct
3 Correct 359 ms 62144 KB Output is correct
4 Correct 345 ms 62552 KB Output is correct
5 Correct 347 ms 62504 KB Output is correct
6 Correct 359 ms 62512 KB Output is correct
7 Correct 423 ms 62608 KB Output is correct
8 Correct 332 ms 62128 KB Output is correct
9 Correct 369 ms 62420 KB Output is correct
10 Correct 342 ms 62004 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47340 KB Output is correct
2 Correct 27 ms 47188 KB Output is correct
3 Correct 24 ms 47284 KB Output is correct
4 Correct 25 ms 47316 KB Output is correct
5 Correct 23 ms 47284 KB Output is correct
6 Correct 27 ms 47308 KB Output is correct
7 Correct 26 ms 47316 KB Output is correct
8 Correct 23 ms 47300 KB Output is correct
9 Incorrect 22 ms 47188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 47188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47340 KB Output is correct
2 Correct 27 ms 47188 KB Output is correct
3 Correct 24 ms 47284 KB Output is correct
4 Correct 25 ms 47316 KB Output is correct
5 Correct 23 ms 47284 KB Output is correct
6 Correct 27 ms 47308 KB Output is correct
7 Correct 26 ms 47316 KB Output is correct
8 Correct 23 ms 47300 KB Output is correct
9 Correct 92 ms 56452 KB Output is correct
10 Correct 99 ms 58676 KB Output is correct
11 Correct 104 ms 58368 KB Output is correct
12 Correct 117 ms 59020 KB Output is correct
13 Correct 98 ms 58904 KB Output is correct
14 Correct 90 ms 56596 KB Output is correct
15 Correct 158 ms 60548 KB Output is correct
16 Correct 170 ms 60180 KB Output is correct
17 Correct 148 ms 60772 KB Output is correct
18 Correct 155 ms 60732 KB Output is correct
19 Correct 359 ms 62144 KB Output is correct
20 Correct 345 ms 62552 KB Output is correct
21 Correct 347 ms 62504 KB Output is correct
22 Correct 359 ms 62512 KB Output is correct
23 Correct 423 ms 62608 KB Output is correct
24 Correct 332 ms 62128 KB Output is correct
25 Correct 369 ms 62420 KB Output is correct
26 Correct 342 ms 62004 KB Output is correct
27 Correct 23 ms 47440 KB Output is correct
28 Correct 25 ms 47424 KB Output is correct
29 Correct 26 ms 47432 KB Output is correct
30 Correct 25 ms 47416 KB Output is correct
31 Correct 26 ms 47340 KB Output is correct
32 Correct 24 ms 47444 KB Output is correct
33 Correct 27 ms 47436 KB Output is correct
34 Correct 35 ms 47548 KB Output is correct
35 Correct 28 ms 47444 KB Output is correct
36 Correct 103 ms 49468 KB Output is correct
37 Execution timed out 2041 ms 66752 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 47188 KB Output isn't correct
2 Halted 0 ms 0 KB -