oj.uz

Submission #396841

# Submission time Handle Problem Language Result Execution time Memory
396841 2021-04-30T19:37:50 Z duality Robot (JOI21_ho_t4) C++11
100 / 100
 1332 ms 51048 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 ----------

struct edge { int v,c; LLI p; };
bool comp(edge a,edge b) {
    return a.c < b.c;
}
vector<edge> adjList[100000],adjList2[100000];
map<pii,LLI> dist;
priority_queue<pair<LLI,pii> > H;
int main() {
    int i;
    int N,M;
    int A,B,C,P;
    scanf("%d %d",&N,&M);
    for (i = 0; i < M; i++) {
        scanf("%d %d %d %d",&A,&B,&C,&P);
        A--,B--,C--;
        adjList[A].pb((edge){B,C,P});
        adjList[B].pb((edge){A,C,P});
    }

    int j,k;
    for (i = 0; i < N; i++) {
        sort(adjList[i].begin(),adjList[i].end(),comp);
        j = 0;
        while (j < adjList[i].size()) {
            k = j;
            LLI sum = 0;
            while ((k < adjList[i].size()) && (adjList[i][j].c == adjList[i][k].c)) sum += adjList[i][k].p,k++;
            int e = k;
            for (k = j; k < e; k++) adjList2[i].pb((edge){adjList[i][k].v,adjList[i][k].c,sum-adjList[i][k].p});
            j = e;
        }
    }
    dist[mp(0,-1)] = 0,H.push(mp(0,mp(0,-1)));
    while (!H.empty()) {
        LLI d = -H.top().first;
        int u = H.top().second.first,c = H.top().second.second;
        H.pop();

        if (d > dist[mp(u,c)]) continue;
        if (c == -1) {
            for (i = 0; i < adjList[u].size(); i++) {
                int v = adjList[u][i].v;
                if (!dist.count(mp(v,-1)) || (d+adjList[u][i].p < dist[mp(v,-1)])) {
                    dist[mp(v,-1)] = d+adjList[u][i].p;
                    H.push(mp(-dist[mp(v,-1)],mp(v,-1)));
                }
            }
            for (i = 0; i < adjList2[u].size(); i++) {
                int v = adjList2[u][i].v,c2 = adjList2[u][i].c;
                if (!dist.count(mp(v,-1)) || (d+adjList2[u][i].p < dist[mp(v,-1)])) {
                    dist[mp(v,-1)] = d+adjList2[u][i].p;
                    H.push(mp(-dist[mp(v,-1)],mp(v,-1)));
                }
                if (!dist.count(mp(v,c2)) || (d < dist[mp(v,c2)])) {
                    dist[mp(v,c2)] = d;
                    H.push(mp(-dist[mp(v,c2)],mp(v,c2)));
                }
            }
        }
        else {
            i = lower_bound(adjList2[u].begin(),adjList2[u].end(),(edge){-1,c,-1},comp)-adjList2[u].begin();
            for (; (i < adjList2[u].size()) && (adjList2[u][i].c == c); i++) {
                int v = adjList2[u][i].v;
                if (!dist.count(mp(v,-1)) || (d+adjList2[u][i].p < dist[mp(v,-1)])) {
                    dist[mp(v,-1)] = d+adjList2[u][i].p;
                    H.push(mp(-dist[mp(v,-1)],mp(v,-1)));
                }
            }
        }
    }
    if (!dist.count(mp(N-1,-1))) printf("-1\n");
    else printf("%lld\n",dist[mp(N-1,-1)]);

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         while (j < adjList[i].size()) {
      |                ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             while ((k < adjList[i].size()) && (adjList[i][j].c == adjList[i][k].c)) sum += adjList[i][k].p,k++;
      |                     ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             for (i = 0; i < adjList[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             for (i = 0; i < adjList2[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             for (; (i < adjList2[u].size()) && (adjList2[u][i].c == c); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |         scanf("%d %d %d %d",&A,&B,&C,&P);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 5004 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 4996 KB Output is correct
7 Correct 6 ms 5132 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 9 ms 5324 KB Output is correct
10 Correct 8 ms 5324 KB Output is correct
11 Correct 7 ms 5324 KB Output is correct
12 Correct 7 ms 5324 KB Output is correct
13 Correct 9 ms 5324 KB Output is correct
14 Correct 9 ms 5324 KB Output is correct
15 Correct 8 ms 5136 KB Output is correct
16 Correct 9 ms 5360 KB Output is correct
17 Correct 9 ms 5196 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 7 ms 5196 KB Output is correct
20 Correct 7 ms 5268 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 19616 KB Output is correct
2 Correct 164 ms 12464 KB Output is correct
3 Correct 560 ms 21928 KB Output is correct
4 Correct 246 ms 15452 KB Output is correct
5 Correct 1200 ms 45996 KB Output is correct
6 Correct 973 ms 42184 KB Output is correct
7 Correct 771 ms 37576 KB Output is correct
8 Correct 917 ms 37280 KB Output is correct
9 Correct 1034 ms 37356 KB Output is correct
10 Correct 555 ms 26096 KB Output is correct
11 Correct 84 ms 15100 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 5004 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 4996 KB Output is correct
7 Correct 6 ms 5132 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 9 ms 5324 KB Output is correct
10 Correct 8 ms 5324 KB Output is correct
11 Correct 7 ms 5324 KB Output is correct
12 Correct 7 ms 5324 KB Output is correct
13 Correct 9 ms 5324 KB Output is correct
14 Correct 9 ms 5324 KB Output is correct
15 Correct 8 ms 5136 KB Output is correct
16 Correct 9 ms 5360 KB Output is correct
17 Correct 9 ms 5196 KB Output is correct
18 Correct 4 ms 4940 KB Output is correct
19 Correct 7 ms 5196 KB Output is correct
20 Correct 7 ms 5268 KB Output is correct
21 Correct 412 ms 19616 KB Output is correct
22 Correct 164 ms 12464 KB Output is correct
23 Correct 560 ms 21928 KB Output is correct
24 Correct 246 ms 15452 KB Output is correct
25 Correct 1200 ms 45996 KB Output is correct
26 Correct 973 ms 42184 KB Output is correct
27 Correct 771 ms 37576 KB Output is correct
28 Correct 917 ms 37280 KB Output is correct
29 Correct 1034 ms 37356 KB Output is correct
30 Correct 555 ms 26096 KB Output is correct
31 Correct 84 ms 15100 KB Output is correct
32 Correct 405 ms 21748 KB Output is correct
33 Correct 486 ms 22720 KB Output is correct
34 Correct 867 ms 32800 KB Output is correct
35 Correct 663 ms 27620 KB Output is correct
36 Correct 671 ms 32824 KB Output is correct
37 Correct 809 ms 36392 KB Output is correct
38 Correct 898 ms 43240 KB Output is correct
39 Correct 470 ms 28436 KB Output is correct
40 Correct 974 ms 42180 KB Output is correct
41 Correct 1235 ms 42336 KB Output is correct
42 Correct 1072 ms 40228 KB Output is correct
43 Correct 339 ms 20756 KB Output is correct
44 Correct 915 ms 34016 KB Output is correct
45 Correct 851 ms 36128 KB Output is correct
46 Correct 692 ms 35068 KB Output is correct
47 Correct 809 ms 35444 KB Output is correct
48 Correct 1332 ms 51048 KB Output is correct