oj.uz

Submission #735446

# Submission time Handle Problem Language Result Execution time Memory
735446 2023-05-04T07:00:15 Z Nahian9696 Swapping Cities (APIO20_swap) C++17
13 / 100
 132 ms 11312 KB 
#include "swap.h"

#include <iostream>
#include <iomanip>
#include <chrono>

#include <cmath>
#include <cstring>
#include <algorithm>


#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <string>
#include <vector>
#include <bitset>



using std::min;
using std::max;
using std::sort;
using std::swap;
using std::fixed;
using std::to_string;
using std::make_pair;
using std::upper_bound;
using std::lower_bound;
using std::setprecision;

using std::cin;
using std::cout;

using std::set;
using std::map;
using std::list;
using std::pair;
using std::less;
using std::tuple;
using std::stack;
using std::queue;
using std::deque;
using std::string;
using std::vector;
using std::bitset;
using std::greater;
using std::priority_queue;





typedef long double                         ld;
typedef unsigned                            ui;
typedef long long                           lli;
typedef unsigned long long                  ulli;
typedef vector<int32_t>                     vi;
typedef vector<ld>                          vld;
typedef vector<ui>                          vui;
typedef vector<lli>                         vlli;
typedef vector<ulli>                        vulli;
typedef list<int32_t>                       lsi;
typedef list<ld>                            lsld;
typedef list<ui>                            lsui;
typedef list<lli>                           lslli;
typedef list<ulli>                          lsulli;
typedef set<int32_t>                        si;
typedef set<ld>                             sld;
typedef set<ui>                             sui;
typedef set<lli>                            slli;
typedef set<ulli>                           sulli;

typedef pair<int32_t, int32_t>              pii;
typedef pair<lli, lli>                      pll;



// #define int                                 int64_t

#define endl                                "\n"
#define inp(n)                              int n; cin >> n
#define Inp(n)                              lli n; cin >> n
#define inpstr(s)                           string s; cin >> s
#define inp2(a,b)                           int a,b; cin >> a >> b
#define Inp2(a,b)                           lli a,b; cin >> a >> b
#define inparr(arr,n)                       int arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define Inparr(arr,n)                       lli arr[n]; f0(t_ind, n) cin >> arr[t_ind]

#define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
#define f1(i,n)                             for(int32_t i = 1; i <= (n); i++)
#define rep0(i,l,r)                         for(int32_t i=(l); i <  (r); i++)
#define rep1(i,l,r)                         for(int32_t i=(l); i <= (r); i++)

#define testIn                              cin >> test
#define tests                               for(int32_t testNo=1; testNo <= (test); testNo++)

#define all(x)                              (x).begin(), (x).end()
#define rall(x)                             (x).rbegin(), (x).rend()
#define asrt(v)                             sort(all(v))
#define dsrt(v)                             sort(rall(v))
#define revStr(str)                         string(rall(str))
#define len(a)                              ((int64_t)(a).size())
#define front_zero(n)                       __builtin_clzll(n)
#define back_zero(n)                        __builtin_ctzll(n)
#define total_one(n)                        __builtin_popcountll(n)
#define lcm(a, b)                           (((a)*(b))/gcd(a,b))
#define mem(a, b)                           memset(a, b, sizeof(a))

#define pb                                  push_back
#define pf                                  push_front
#define mp                                  make_pair
#define ff                                  first
#define ss                                  second

#define yes                                 cout << "yes" << endl
#define no                                  cout << "no" << endl
#define Yes                                 cout << "Yes" << endl
#define No                                  cout << "No" << endl
#define YES                                 cout << "YES" << endl
#define NO                                  cout << "NO" << endl
#define finish                              return 0
#define clean                               fflush(stdout)

#define Inf                                 (int32_t)(1e9)
#define INF                                 (lli)(1e18)
#define Eps                                 (ld)(1e-9)
#define EPS                                 (ld)(1e-18)
#define PI                                  (ld)(3.141592653589793238462643383279502884197169L)
#define MOD                                 (int32_t)(1e9+7)
#define MXN                                 (int32_t)(1e5+7)




bool cycle = false, line = false;
int n;
vector<pii> str;
int stval[100005];
int mx = 0;


void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    

    n = N;

    if(M == N) {
        cycle = true;
        f0(i, M) {
            mx = max(mx, W[i]);
        }
    } else {
        int deg[N] = {0};
        f0(i, M) {
            deg[U[i]]++;
            deg[V[i]]++;
        }
        if(deg[0] <= 2) line = true;
    }
    if(!line) {
        f0(i, M) {
            stval[V[i]] = W[i];
            str.pb({W[i], V[i]});
        }
        sort(all(str));
    }
}

int getMinimumFuelCapacity(int X, int Y) {

    if(cycle) {
        return mx;
    }

    if(line) {
        return -1;
    }

    vi ans;

    if(X != 0) ans.pb(stval[X]);
    if(Y!= 0) ans.pb(stval[Y]);

    for(auto p: str) {
        if((p.ss != X) && (p.ss != Y)) {
            ans.pb(p.ff);
        }
        if(ans.size() == 3) break;
    }

    return max({ans[0], ans[1], ans[2]});

    // if(X > Y) swap(X, Y);
    // if(X == 0) {

    // } else {

    // }


    return -1;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 24 ms 2388 KB Output is correct
10 Correct 29 ms 2892 KB Output is correct
11 Correct 31 ms 2840 KB Output is correct
12 Correct 42 ms 3008 KB Output is correct
13 Correct 29 ms 3028 KB Output is correct
14 Correct 27 ms 2544 KB Output is correct
15 Correct 78 ms 4680 KB Output is correct
16 Correct 75 ms 4664 KB Output is correct
17 Correct 81 ms 4788 KB Output is correct
18 Correct 82 ms 4816 KB Output is correct
19 Correct 46 ms 4364 KB Output is correct
20 Correct 88 ms 6736 KB Output is correct
21 Correct 92 ms 6972 KB Output is correct
22 Correct 90 ms 7208 KB Output is correct
23 Correct 90 ms 7088 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 114 ms 7140 KB Output is correct
4 Correct 105 ms 10032 KB Output is correct
5 Correct 113 ms 10256 KB Output is correct
6 Correct 132 ms 10912 KB Output is correct
7 Correct 119 ms 11312 KB Output is correct
8 Correct 123 ms 10976 KB Output is correct
9 Correct 112 ms 11144 KB Output is correct
10 Correct 118 ms 11004 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 212 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 212 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 24 ms 2388 KB Output is correct
10 Correct 29 ms 2892 KB Output is correct
11 Correct 31 ms 2840 KB Output is correct
12 Correct 42 ms 3008 KB Output is correct
13 Correct 29 ms 3028 KB Output is correct
14 Correct 27 ms 2544 KB Output is correct
15 Correct 78 ms 4680 KB Output is correct
16 Correct 75 ms 4664 KB Output is correct
17 Correct 81 ms 4788 KB Output is correct
18 Correct 82 ms 4816 KB Output is correct
19 Correct 114 ms 7140 KB Output is correct
20 Correct 105 ms 10032 KB Output is correct
21 Correct 113 ms 10256 KB Output is correct
22 Correct 132 ms 10912 KB Output is correct
23 Correct 119 ms 11312 KB Output is correct
24 Correct 123 ms 10976 KB Output is correct
25 Correct 112 ms 11144 KB Output is correct
26 Correct 118 ms 11004 KB Output is correct
27 Incorrect 1 ms 324 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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