oj.uz

Submission #551789

# Submission time Handle Problem Language Result Execution time Memory
551789 2022-04-21T14:34:33 Z nicolaalexandra Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 19688 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)
        return -1;

    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
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 3 ms 4948 KB Output is correct
4 Correct 3 ms 5016 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 4 ms 5020 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 44 ms 11800 KB Output is correct
10 Correct 74 ms 13404 KB Output is correct
11 Correct 46 ms 13164 KB Output is correct
12 Correct 50 ms 13712 KB Output is correct
13 Correct 53 ms 13720 KB Output is correct
14 Correct 51 ms 12108 KB Output is correct
15 Correct 108 ms 17652 KB Output is correct
16 Correct 102 ms 17352 KB Output is correct
17 Correct 109 ms 17836 KB Output is correct
18 Correct 116 ms 17760 KB Output is correct
19 Incorrect 56 ms 10340 KB Output isn't correct
20 Halted 0 ms 0 KB -

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 2065 ms 19688 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 3 ms 4948 KB Output is correct
4 Correct 3 ms 5016 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 4 ms 5020 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Incorrect 5 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 5 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 3 ms 4948 KB Output is correct
4 Correct 3 ms 5016 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 4 ms 5020 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 44 ms 11800 KB Output is correct
10 Correct 74 ms 13404 KB Output is correct
11 Correct 46 ms 13164 KB Output is correct
12 Correct 50 ms 13712 KB Output is correct
13 Correct 53 ms 13720 KB Output is correct
14 Correct 51 ms 12108 KB Output is correct
15 Correct 108 ms 17652 KB Output is correct
16 Correct 102 ms 17352 KB Output is correct
17 Correct 109 ms 17836 KB Output is correct
18 Correct 116 ms 17760 KB Output is correct
19 Execution timed out 2065 ms 19688 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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