oj.uz

Submission #135216

# Submission time Handle Problem Language Result Execution time Memory
135216 2019-07-23T20:18:59 Z duality Commuter Pass (JOI18_commuter_pass) C++11
100 / 100
 495 ms 20948 KB 
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

vpii adjList[100000];
LLI distS[100000],distT[100000],distU[100000],distV[100000];
priority_queue<pair<LLI,int> > H;
int findDist(int s,LLI *dist,int N) {
    int i;
    for (i = 0; i < N; i++) dist[i] = -1;
    dist[s] = 0,H.push(mp(0,s));
    while (!H.empty()) {
        int u = H.top().second;
        LLI d = -H.top().first;
        H.pop();

        if (d > dist[u]) continue;
        for (i = 0; i < adjList[u].size(); i++) {
            int v = adjList[u][i].first;
            if ((dist[v] == -1) || (d+adjList[u][i].second < dist[v])) {
                dist[v] = d+adjList[u][i].second;
                H.push(mp(-dist[v],v));
            }
        }
    }
    return 0;
}
LLI dist1[100000],dist2[100000];
int visited[100000];
LLI doDFS(int u,LLI *a,LLI *b,LLI *c) {
    if (visited[u]) return c[u];
    int i;
    visited[u] = 1,c[u] = b[u];
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i].first;
        if (a[u] == a[v]+adjList[u][i].second) c[u] = min(c[u],doDFS(v,a,b,c));
    }
    return c[u];
}
int main() {
    int i;
    int N,M;
    int S,T,U,V;
    int A,B,C;
    scanf("%d %d %d %d %d %d",&N,&M,&S,&T,&U,&V);
    S--,T--,U--,V--;
    for (i = 0; i < M; i++) {
        scanf("%d %d %d",&A,&B,&C);
        A--,B--;
        adjList[A].pb(mp(B,C));
        adjList[B].pb(mp(A,C));
    }

    findDist(S,distS,N),findDist(T,distT,N);
    findDist(U,distU,N),findDist(V,distV,N);
    LLI ans = distU[V];
    for (i = 0; i < N; i++) doDFS(i,distS,distU,dist1);
    fill(visited,visited+N,0);
    for (i = 0; i < N; i++) doDFS(i,distT,distV,dist2);
    for (i = 0; i < N; i++) {
        if (distS[i]+distT[i] == distS[T]) ans = min(ans,dist1[i]+dist2[i]);
    }
    fill(visited,visited+N,0);
    for (i = 0; i < N; i++) doDFS(i,distS,distV,dist1);
    fill(visited,visited+N,0);
    for (i = 0; i < N; i++) doDFS(i,distT,distU,dist2);
    for (i = 0; i < N; i++) {
        if (distS[i]+distT[i] == distS[T]) ans = min(ans,dist1[i]+dist2[i]);
    }
    printf("%lld\n",ans);

    return 0;
}

Compilation message

commuter_pass.cpp: In function 'int findDist(int, LLI*, int)':
commuter_pass.cpp:71:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'LLI doDFS(int, LLI*, LLI*, LLI*)':
commuter_pass.cpp:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d %d %d",&N,&M,&S,&T,&U,&V);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&A,&B,&C);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 16612 KB Output is correct
2 Correct 454 ms 16744 KB Output is correct
3 Correct 384 ms 19548 KB Output is correct
4 Correct 380 ms 16760 KB Output is correct
5 Correct 389 ms 16488 KB Output is correct
6 Correct 398 ms 16736 KB Output is correct
7 Correct 425 ms 16876 KB Output is correct
8 Correct 438 ms 16744 KB Output is correct
9 Correct 392 ms 16292 KB Output is correct
10 Correct 404 ms 16204 KB Output is correct
11 Correct 191 ms 16504 KB Output is correct
12 Correct 395 ms 16360 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 18680 KB Output is correct
2 Correct 415 ms 18280 KB Output is correct
3 Correct 418 ms 19728 KB Output is correct
4 Correct 419 ms 19824 KB Output is correct
5 Correct 418 ms 19564 KB Output is correct
6 Correct 495 ms 20272 KB Output is correct
7 Correct 458 ms 20948 KB Output is correct
8 Correct 431 ms 19432 KB Output is correct
9 Correct 426 ms 17900 KB Output is correct
10 Correct 495 ms 18536 KB Output is correct
11 Correct 211 ms 16660 KB Output is correct
12 Correct 488 ms 19884 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3708 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Correct 4 ms 2684 KB Output is correct
4 Correct 26 ms 4856 KB Output is correct
5 Correct 15 ms 3832 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 6 ms 2808 KB Output is correct
8 Correct 6 ms 2936 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 16 ms 3832 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 5 ms 2808 KB Output is correct
13 Correct 5 ms 2808 KB Output is correct
14 Correct 6 ms 2808 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 16612 KB Output is correct
2 Correct 454 ms 16744 KB Output is correct
3 Correct 384 ms 19548 KB Output is correct
4 Correct 380 ms 16760 KB Output is correct
5 Correct 389 ms 16488 KB Output is correct
6 Correct 398 ms 16736 KB Output is correct
7 Correct 425 ms 16876 KB Output is correct
8 Correct 438 ms 16744 KB Output is correct
9 Correct 392 ms 16292 KB Output is correct
10 Correct 404 ms 16204 KB Output is correct
11 Correct 191 ms 16504 KB Output is correct
12 Correct 395 ms 16360 KB Output is correct
13 Correct 427 ms 18680 KB Output is correct
14 Correct 415 ms 18280 KB Output is correct
15 Correct 418 ms 19728 KB Output is correct
16 Correct 419 ms 19824 KB Output is correct
17 Correct 418 ms 19564 KB Output is correct
18 Correct 495 ms 20272 KB Output is correct
19 Correct 458 ms 20948 KB Output is correct
20 Correct 431 ms 19432 KB Output is correct
21 Correct 426 ms 17900 KB Output is correct
22 Correct 495 ms 18536 KB Output is correct
23 Correct 211 ms 16660 KB Output is correct
24 Correct 488 ms 19884 KB Output is correct
25 Correct 15 ms 3708 KB Output is correct
26 Correct 5 ms 2808 KB Output is correct
27 Correct 4 ms 2684 KB Output is correct
28 Correct 26 ms 4856 KB Output is correct
29 Correct 15 ms 3832 KB Output is correct
30 Correct 5 ms 2808 KB Output is correct
31 Correct 6 ms 2808 KB Output is correct
32 Correct 6 ms 2936 KB Output is correct
33 Correct 5 ms 2808 KB Output is correct
34 Correct 16 ms 3832 KB Output is correct
35 Correct 5 ms 2808 KB Output is correct
36 Correct 5 ms 2808 KB Output is correct
37 Correct 5 ms 2808 KB Output is correct
38 Correct 6 ms 2808 KB Output is correct
39 Correct 5 ms 2808 KB Output is correct
40 Correct 399 ms 16784 KB Output is correct
41 Correct 385 ms 16360 KB Output is correct
42 Correct 401 ms 16620 KB Output is correct
43 Correct 157 ms 15736 KB Output is correct
44 Correct 309 ms 15976 KB Output is correct
45 Correct 416 ms 16236 KB Output is correct
46 Correct 360 ms 16104 KB Output is correct
47 Correct 383 ms 16636 KB Output is correct
48 Correct 160 ms 13560 KB Output is correct
49 Correct 301 ms 16600 KB Output is correct
50 Correct 397 ms 16268 KB Output is correct
51 Correct 336 ms 16108 KB Output is correct