oj.uz

Submission #979391

# Submission time Handle Problem Language Result Execution time Memory
979391 2024-05-10T18:52:43 Z Mher777 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 16056 KB 
#include "swap.h"
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
using namespace std;
mt19937 rnd(7069);
typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef float fl;
typedef long double ld;
using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define all(x) (x).begin(), (x).end()
const int dx[8] = { -1, 0, 1, 0, -1, -1, 1, 1 };
const int dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };
const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18) + 5ll;
const ll MOD = ll(1000000007);
const ll MOD2 = ll(998244353);

const int N = 100005;
int used[N];
vector<pii> g[N];
int n, m;
int l, r, mid, x, y, ans;
bool f = false;

void init(int N, int M, vi U, vi V, vi W) {
    n = N, m = M;
    for (int i = 0; i < m; ++i) {
        g[U[i]].pub({ W[i], V[i] });
        g[V[i]].pub({ W[i],U[i] });
    }
    for (int i = 0; i < n; ++i) {
        sort(all(g[i]));
    }
}

void dfs(int u, bool fx = false) {
    if (u == y && fx) {
        f = true;
    }
    if (u == y) return;
    used[u] = 1;
    int dep = upper_bound(all(g[u]), mpr(mid, MAX)) - g[u].begin();
    for (auto to : g[u]) {
        if (to.ff > mid) break;
        if (used[to.ss] && to.ss == y) {
            f = true;
            continue;
        }
        if (used[to.ss]) continue;
        if (u == x) {
            dfs(to.ss, fx);
            continue;
        }
        if (dep >= 3) {
            dfs(to.ss, true);
            continue;
        }
        dfs(to.ss, fx);
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    x = X, y = Y;
    l = 0, r = 1e9;
    ans = -1;
    while (l <= r) {
        mid = (l + r) / 2;
        f = false;
        for (int i = 0; i < n; ++i) {
            used[i] = 0;
        }
        dfs(x);
        if (f) {
            r = mid - 1;
            ans = mid;
        }
        else {
            l = mid + 1;
        }
    }
    return ans;
}

/*
1.
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

2.
3 2
0 1 5
0 2 5
1
1 2

answers
1.
3
10
4

2.
-1
*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2916 KB Output is correct
7 Correct 2 ms 2860 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 106 ms 11480 KB Output is correct
10 Correct 214 ms 15588 KB Output is correct
11 Correct 354 ms 15328 KB Output is correct
12 Correct 353 ms 16056 KB Output is correct
13 Correct 416 ms 15656 KB Output is correct
14 Execution timed out 2029 ms 14004 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Execution timed out 2012 ms 10120 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2916 KB Output is correct
7 Correct 2 ms 2860 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Incorrect 1 ms 2652 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2916 KB Output is correct
7 Correct 2 ms 2860 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 106 ms 11480 KB Output is correct
10 Correct 214 ms 15588 KB Output is correct
11 Correct 354 ms 15328 KB Output is correct
12 Correct 353 ms 16056 KB Output is correct
13 Correct 416 ms 15656 KB Output is correct
14 Execution timed out 2029 ms 14004 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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