oj.uz

Submission #682954

# Submission time Handle Problem Language Result Execution time Memory
682954 2023-01-17T10:59:09 Z Nursik Swapping Cities (APIO20_swap) C++14
13 / 100
 381 ms 62456 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);
       // cout << xu << " " << yu << '\n';
        cycle = 0;
        for (int i = 0; i < ver; ++i){
            used[i] = 0;
        }
        dfs(x, -1);
       /* for (int i = 0; i < ver; ++i){
            cout << used[i] << " ";
        }
        cout << '\n';
        cout << cycle << '\n';*/
        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){
                    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 22 ms 47188 KB Output is correct
3 Correct 23 ms 47188 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Correct 24 ms 47276 KB Output is correct
6 Correct 23 ms 47312 KB Output is correct
7 Correct 24 ms 47304 KB Output is correct
8 Correct 23 ms 47340 KB Output is correct
9 Correct 80 ms 56316 KB Output is correct
10 Correct 101 ms 58264 KB Output is correct
11 Correct 96 ms 58188 KB Output is correct
12 Correct 108 ms 58768 KB Output is correct
13 Correct 105 ms 58764 KB Output is correct
14 Correct 86 ms 56452 KB Output is correct
15 Correct 165 ms 60192 KB Output is correct
16 Correct 157 ms 60052 KB Output is correct
17 Correct 161 ms 60592 KB Output is correct
18 Correct 157 ms 60680 KB Output is correct
19 Correct 78 ms 52636 KB Output is correct
20 Correct 148 ms 61440 KB Output is correct
21 Correct 155 ms 61332 KB Output is correct
22 Correct 184 ms 61952 KB Output is correct
23 Correct 158 ms 62008 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 22 ms 47188 KB Output is correct
3 Correct 367 ms 62000 KB Output is correct
4 Correct 321 ms 62456 KB Output is correct
5 Correct 344 ms 62348 KB Output is correct
6 Correct 321 ms 62292 KB Output is correct
7 Correct 347 ms 62404 KB Output is correct
8 Correct 381 ms 61960 KB Output is correct
9 Correct 336 ms 62184 KB Output is correct
10 Correct 339 ms 61956 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 22 ms 47188 KB Output is correct
3 Correct 23 ms 47188 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Correct 24 ms 47276 KB Output is correct
6 Correct 23 ms 47312 KB Output is correct
7 Correct 24 ms 47304 KB Output is correct
8 Correct 23 ms 47340 KB Output is correct
9 Incorrect 23 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 23 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 23 ms 47188 KB Output is correct
2 Correct 22 ms 47188 KB Output is correct
3 Correct 23 ms 47188 KB Output is correct
4 Correct 23 ms 47316 KB Output is correct
5 Correct 24 ms 47276 KB Output is correct
6 Correct 23 ms 47312 KB Output is correct
7 Correct 24 ms 47304 KB Output is correct
8 Correct 23 ms 47340 KB Output is correct
9 Correct 80 ms 56316 KB Output is correct
10 Correct 101 ms 58264 KB Output is correct
11 Correct 96 ms 58188 KB Output is correct
12 Correct 108 ms 58768 KB Output is correct
13 Correct 105 ms 58764 KB Output is correct
14 Correct 86 ms 56452 KB Output is correct
15 Correct 165 ms 60192 KB Output is correct
16 Correct 157 ms 60052 KB Output is correct
17 Correct 161 ms 60592 KB Output is correct
18 Correct 157 ms 60680 KB Output is correct
19 Correct 367 ms 62000 KB Output is correct
20 Correct 321 ms 62456 KB Output is correct
21 Correct 344 ms 62348 KB Output is correct
22 Correct 321 ms 62292 KB Output is correct
23 Correct 347 ms 62404 KB Output is correct
24 Correct 381 ms 61960 KB Output is correct
25 Correct 336 ms 62184 KB Output is correct
26 Correct 339 ms 61956 KB Output is correct
27 Correct 24 ms 47380 KB Output is correct
28 Correct 24 ms 47448 KB Output is correct
29 Correct 25 ms 47372 KB Output is correct
30 Correct 25 ms 47404 KB Output is correct
31 Correct 29 ms 47436 KB Output is correct
32 Incorrect 24 ms 47452 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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