oj.uz

Submission #551790

# Submission time Handle Problem Language Result Execution time Memory
551790 2022-04-21T14:36:39 Z nicolaalexandra Swapping Cities (APIO20_swap) C++14
6 / 100
 2000 ms 19352 KB 
#include <bits/stdc++.h>
#include "swap.h"
#define DIM 200010
#define INF 2000000000
using namespace std;

struct muchie{
    int x,y,cost;
} mch[DIM];

priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > h;
vector<pair <int,int> > L[DIM];
deque <int> c;
int dist[DIM],t[DIM],cnt[DIM],f[DIM],viz[DIM],mrk[DIM];
int n,m,subtask,maxi;

void dijkstra (int start, int dist[], int cnt[], int t[]){

    for (int i=1;i<=n;i++){
        dist[i] = INF;
        cnt[i] = 0;
        t[i] = 0;
    }

    while (!h.empty())
        h.pop();

    dist[start] = 0;
    cnt[start] = 1;
    h.push(make_pair(dist[start],start));
    while (!h.empty()){
        int nod = h.top().second, cost = h.top().first;
        h.pop();
        if (dist[nod] != cost)
            continue;

        for (auto it : L[nod]){
            int vecin = it.first, cst = it.second;
            if (dist[nod] + cst < dist[vecin]){
                dist[vecin] = dist[nod] + cst;
                cnt[vecin] = cnt[nod];
                t[vecin] = nod;
                h.push(make_pair(dist[vecin],vecin));
            } else {
                if (dist[nod] + cst == dist[vecin])
                    cnt[vecin] += cnt[nod];
            }
        }
    }
}

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

    n = N, m = M;
    for (int i=0;i<m;i++){
        int x = U[i], y = V[i], cost = W[i];
        x++, y++;

        L[x].push_back(make_pair(y,cost));
        L[y].push_back(make_pair(x,cost));
        maxi = max (maxi,cost);

        mch[i+1] = {x,y,cost};
    }

    subtask = 1;
    for (int i=1;i<=n;i++)
        if (L[i].size() > 2)
            subtask = 0;

}

void dfs (int nod, int val){
    viz[nod] = 1;
    for (auto it : L[nod]){
        if (it.second > val || mrk[it.first] || viz[it.first])
            continue;
        dfs (it.first,val);
    }
}

inline int verif (int val, int x, int y){

    memset (viz,0,sizeof viz);
    memset (t,0,sizeof t);
    memset (mrk,0,sizeof mrk);

    c.clear();
    c.push_back(x);
    viz[x] = 1;

    int ok = 0;
    while (!c.empty()){
        int nod = c.front();
        c.pop_front();

        int cnt = 0;
        for (auto it : L[nod]){
            int vecin = it.first, cost = it.second;
            if (cost > val)
                continue;
            if (!viz[vecin]){
                viz[vecin] = 1 + viz[nod];
                t[vecin] = nod;
                c.push_back(vecin);
            }

            cnt++;
        }

        if (cnt > 2 && nod != x && nod != y)
            ok = 1;
    }

    if (!viz[y])
        return 0;

    if (ok)
        return 1;

    /// exista doua drumuri disjuncte intre x si y?
    int nod = y;
    while (nod){
        if (nod != y)
            mrk[nod] = 1;
        nod = t[nod];
    }

    memset (viz,0,sizeof viz);

    dfs (x,val);

    if (viz[y])
        return 1;

    return 0;
}

int getMinimumFuelCapacity(int x, int y) {

    if (subtask == 1){
        if (m == n-1)
            return -1;
        else return maxi;
    }

    x++, y++;

    int st = 1, dr = maxi, sol = -1;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif(mid,x,y)){
            sol = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    return sol;


}
/*
int main (){

    FILE *fin = fopen ("date.in", "r");
    FILE *fout = fopen ("date.out", "w");

    int N, M;
    assert(2 == fscanf(fin, "%d %d", &N, &M));

    std::vector<int> U(M), V(M), W(M);
    for (int i = 0; i < M; ++i) {
        assert(3 == fscanf(fin, "%d %d %d", &U[i], &V[i], &W[i]));
    }

    int Q;
    assert(1 == fscanf(fin,"%d", &Q));

    std::vector<int> X(Q), Y(Q);
    for (int i = 0; i < Q; ++i) {
        assert(2 == fscanf(fin,"%d %d", &X[i], &Y[i]));
    }

    init(N, M, U, V, W);

    std::vector<int> minimum_fuel_capacities(Q);
    for (int i = 0; i < Q; ++i) {
        minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
    }

    for (int i = 0; i < Q; ++i) {
        fprintf(fout, "%d\n", minimum_fuel_capacities[i]);
    }



    return 0;
}*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 41 ms 10152 KB Output is correct
10 Correct 45 ms 11396 KB Output is correct
11 Correct 43 ms 11252 KB Output is correct
12 Correct 47 ms 11568 KB Output is correct
13 Correct 52 ms 11552 KB Output is correct
14 Correct 43 ms 10284 KB Output is correct
15 Correct 104 ms 13144 KB Output is correct
16 Correct 101 ms 13076 KB Output is correct
17 Correct 94 ms 13332 KB Output is correct
18 Correct 105 ms 13328 KB Output is correct
19 Correct 57 ms 9508 KB Output is correct
20 Correct 100 ms 18584 KB Output is correct
21 Correct 98 ms 18692 KB Output is correct
22 Correct 115 ms 19352 KB Output is correct
23 Correct 107 ms 19240 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 41 ms 10152 KB Output is correct
10 Correct 45 ms 11396 KB Output is correct
11 Correct 43 ms 11252 KB Output is correct
12 Correct 47 ms 11568 KB Output is correct
13 Correct 52 ms 11552 KB Output is correct
14 Correct 43 ms 10284 KB Output is correct
15 Correct 104 ms 13144 KB Output is correct
16 Correct 101 ms 13076 KB Output is correct
17 Correct 94 ms 13332 KB Output is correct
18 Correct 105 ms 13328 KB Output is correct
19 Execution timed out 2097 ms 15872 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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