oj.uz

Submission #634865

# Submission time Handle Problem Language Result Execution time Memory
634865 2022-08-25T07:27:36 Z mdn2002 Robot (JOI21_ho_t4) C++14
100 / 100
 1121 ms 92296 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

struct edgg {
    long long b , c , p;
};
long long n , m;
map < int , vector < edgg > > gr [100005];
map < int , long long > sum [100005] , dp [100005];
priority_queue < pair < long long , pair < int , int > > > q;
void add ( int x , int y , long long ad )
{
    if ( dp [x] . count ( y ) == 0 || dp [x][y] > ad )
    {
        dp [x][y] = ad;
        q . push ( { - ad , { x , y } } );
    }
}
int main ()
{
    scanf ( "%lld%lld" , &n , &m );

    for ( int i = 0 ; i < m ; i ++ )
    {
        long long x , y , c , p;
        scanf ( "%lld%lld%lld%lld" , &x , &y , &c , &p );

        gr [y][c] . push_back ( { x , c , p } );

        gr [x][c] . push_back ( { y , c , p } );

        sum [x][c] += p;
        sum [y][c] += p;
    }

    dp [1][0] = 0;
    q . push ( { 0 , { 1 , 0 } } );
    long long ans = 1e16;

    while ( q . size () )
    {
        pair < long long , pair < int , int > > p = q . top ();
        q . pop ();

        int x = p . second . first , last = p . second . second;
        if ( - p . first != dp [x][last] ) continue;
        if ( x == n && last == 0 ) ans = min ( ans , dp [x][last] );
        if ( last == 0 )
        {
            for ( auto xx : gr [x] )
            {
                for ( auto uu : xx . second )
                {
                    long long u = uu . b , c = uu . c , p = uu . p , summ = sum [x][c] - p;

                    add ( u , 0 , dp [x][last] + summ );
                    add ( u , 0 , dp [x][last] + p );
                    add ( u , c , dp [x][last] );

                }
            }
        }
        else
        {
            for ( auto uu : gr [x][last] )
            {
                long long u = uu . b , c = uu . c , p = uu . p , summ = sum [x][c] - p;
                int indd = u - 1;
                add ( u , 0 , dp [x][last] + summ );
            }
        }
    }
    if ( ans == 1e16 ) printf ( "-1" );
    else printf ( "%lld" , ans );
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:75:21: warning: unused variable 'indd' [-Wunused-variable]
   75 |                 int indd = u - 1;
      |                     ^~~~
Main.cpp:28:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf ( "%lld%lld" , &n , &m );
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:33:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf ( "%lld%lld%lld%lld" , &x , &y , &c , &p );
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 8 ms 14372 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14292 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 11 ms 15072 KB Output is correct
10 Correct 11 ms 15008 KB Output is correct
11 Correct 11 ms 14804 KB Output is correct
12 Correct 10 ms 14804 KB Output is correct
13 Correct 10 ms 14812 KB Output is correct
14 Correct 9 ms 14804 KB Output is correct
15 Correct 9 ms 14676 KB Output is correct
16 Correct 10 ms 14780 KB Output is correct
17 Correct 10 ms 14804 KB Output is correct
18 Correct 8 ms 14512 KB Output is correct
19 Correct 9 ms 14676 KB Output is correct
20 Correct 9 ms 14748 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 35692 KB Output is correct
2 Correct 106 ms 25272 KB Output is correct
3 Correct 290 ms 32808 KB Output is correct
4 Correct 170 ms 28932 KB Output is correct
5 Correct 1121 ms 86604 KB Output is correct
6 Correct 822 ms 77540 KB Output is correct
7 Correct 408 ms 62416 KB Output is correct
8 Correct 482 ms 55664 KB Output is correct
9 Correct 449 ms 55624 KB Output is correct
10 Correct 338 ms 49200 KB Output is correct
11 Correct 118 ms 31752 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 8 ms 14372 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14292 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 11 ms 15072 KB Output is correct
10 Correct 11 ms 15008 KB Output is correct
11 Correct 11 ms 14804 KB Output is correct
12 Correct 10 ms 14804 KB Output is correct
13 Correct 10 ms 14812 KB Output is correct
14 Correct 9 ms 14804 KB Output is correct
15 Correct 9 ms 14676 KB Output is correct
16 Correct 10 ms 14780 KB Output is correct
17 Correct 10 ms 14804 KB Output is correct
18 Correct 8 ms 14512 KB Output is correct
19 Correct 9 ms 14676 KB Output is correct
20 Correct 9 ms 14748 KB Output is correct
21 Correct 258 ms 35692 KB Output is correct
22 Correct 106 ms 25272 KB Output is correct
23 Correct 290 ms 32808 KB Output is correct
24 Correct 170 ms 28932 KB Output is correct
25 Correct 1121 ms 86604 KB Output is correct
26 Correct 822 ms 77540 KB Output is correct
27 Correct 408 ms 62416 KB Output is correct
28 Correct 482 ms 55664 KB Output is correct
29 Correct 449 ms 55624 KB Output is correct
30 Correct 338 ms 49200 KB Output is correct
31 Correct 118 ms 31752 KB Output is correct
32 Correct 137 ms 28460 KB Output is correct
33 Correct 180 ms 29740 KB Output is correct
34 Correct 441 ms 50980 KB Output is correct
35 Correct 327 ms 42552 KB Output is correct
36 Correct 323 ms 52212 KB Output is correct
37 Correct 384 ms 55568 KB Output is correct
38 Correct 384 ms 62848 KB Output is correct
39 Correct 137 ms 31800 KB Output is correct
40 Correct 414 ms 55560 KB Output is correct
41 Correct 460 ms 55688 KB Output is correct
42 Correct 566 ms 62420 KB Output is correct
43 Correct 222 ms 36612 KB Output is correct
44 Correct 475 ms 42572 KB Output is correct
45 Correct 318 ms 51660 KB Output is correct
46 Correct 277 ms 51800 KB Output is correct
47 Correct 339 ms 54676 KB Output is correct
48 Correct 1020 ms 92296 KB Output is correct