oj.uz

답안 #885922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
885922 2023-12-11T05:14:35 Z Requiem Robot (JOI21_ho_t4) C++17
100 / 100
 668 ms 98348 KB 
#include<bits/stdc++.h>
// #define int long long
#define ll long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define endl "\n"
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define pi 3.14159265359
#define TASKNAME "robot"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; } 
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; } 
using namespace std; 
typedef pair<ll,ll> ii; 
typedef pair<ll,ii> iii; 
typedef vector<ll> vi; 
const int MAXN = 1e5 + 9;
unordered_map<int,vector<iii>> g[MAXN];
unordered_map<int,ll> psum[MAXN];
ll dist[MAXN],n,m;
unordered_map<int,ll> dp[MAXN];
//dp[i]: khoang cach ngan nhat den dinh i.
//dp2[i][c]: khoang cach ngan nhat den i sao cho:
/*
- Ta di qua mot canh co mau c.
- Ta chua to mau lai canh do.
- Ta se roi dinh i de di den 1 dinh khac co mau c va ta se to mau lai cac neighbor cua no.
*/
main() 
{ 
    fast; 
   if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin); 
        freopen(TASKNAME".out","w",stdout); 
   }
   cin>>n>>m;
   for(int i=1;i<=m;i++){
       int u,v,w,c,p;
       cin>>u>>v>>c>>p;
       g[u][c].pb({v,{c,p}});
       g[v][c].pb({u,{c,p}});
       psum[u][c] += p;
       psum[v][c] += p;
   } 
   priority_queue<tuple<ll,int,int>> pq;
   memset(dist,0x3f,sizeof(dist));
   dist[1] = 0;
   pq.push({0,1,0});
    while(!pq.empty()){
        ll du,u,c;
        tie(du,u,c) = pq.top();
        // cerr<<du<<' '<<u<<' '<<c<<endl;
        pq.pop();
        if (c){
            if (dp[u][c] < -du) continue;
            ll v,color,w,cost;
            for(iii e: g[u][c]){
                v = e.fi;
                color = e.se.fi;
                w = e.se.se;
                cost = -du + psum[u][color] - w;
                //we flip i.
                if (dist[v] > cost){
                    dist[v] = cost;
                    pq.push({-dist[v],v,0});
                }
            }
        }
        else{
            if (dist[u] < -du) continue;
            ll v,color,w,cost;
            for(auto &i: g[u]){
                for(iii e: i.se){
                    v = e.fi;
                    color = e.se.fi;
                    w = e.se.se;
                    // cout<<v<<' '<<color<<' '<<w<<endl;
                    cost = -du + psum[u][color] - w;
                    if (dist[v] > cost){
                        dist[v] = cost;
                        pq.push({-dist[v],v,0});
                    }

                    cost = -du + w;
                    if (dist[v] > cost){
                        dist[v] = cost;
                        pq.push({-dist[v],v,0});
                    }

                    cost = -du;
                    if (!dp[v].count(color) or dp[v][color] > cost){
                        dp[v][color] = cost;
                        pq.push({-dp[v][color],v,color});
                    }

                }
            }
        }
    }
    cout<<((dist[n] >= INF) ? -1 : dist[n])<<endl;
    exit(0);
}

Compilation message

Main.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:43:16: warning: unused variable 'w' [-Wunused-variable]
   43 |        int u,v,w,c,p;
      |                ^
Main.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 17496 KB Output is correct
2 Correct 4 ms 17496 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 5 ms 17500 KB Output is correct
6 Correct 5 ms 17500 KB Output is correct
7 Correct 6 ms 17756 KB Output is correct
8 Correct 5 ms 17748 KB Output is correct
9 Correct 7 ms 18268 KB Output is correct
10 Correct 7 ms 18356 KB Output is correct
11 Correct 6 ms 18516 KB Output is correct
12 Correct 6 ms 18008 KB Output is correct
13 Correct 6 ms 18268 KB Output is correct
14 Correct 6 ms 18268 KB Output is correct
15 Correct 5 ms 18012 KB Output is correct
16 Correct 6 ms 18008 KB Output is correct
17 Correct 6 ms 18012 KB Output is correct
18 Correct 5 ms 17852 KB Output is correct
19 Correct 6 ms 17756 KB Output is correct
20 Correct 5 ms 18012 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 39104 KB Output is correct
2 Correct 56 ms 29340 KB Output is correct
3 Correct 145 ms 36840 KB Output is correct
4 Correct 97 ms 34504 KB Output is correct
5 Correct 653 ms 98308 KB Output is correct
6 Correct 636 ms 88940 KB Output is correct
7 Correct 357 ms 79832 KB Output is correct
8 Correct 440 ms 75056 KB Output is correct
9 Correct 463 ms 74940 KB Output is correct
10 Correct 311 ms 55048 KB Output is correct
11 Correct 120 ms 46464 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 17496 KB Output is correct
2 Correct 4 ms 17496 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 5 ms 17500 KB Output is correct
6 Correct 5 ms 17500 KB Output is correct
7 Correct 6 ms 17756 KB Output is correct
8 Correct 5 ms 17748 KB Output is correct
9 Correct 7 ms 18268 KB Output is correct
10 Correct 7 ms 18356 KB Output is correct
11 Correct 6 ms 18516 KB Output is correct
12 Correct 6 ms 18008 KB Output is correct
13 Correct 6 ms 18268 KB Output is correct
14 Correct 6 ms 18268 KB Output is correct
15 Correct 5 ms 18012 KB Output is correct
16 Correct 6 ms 18008 KB Output is correct
17 Correct 6 ms 18012 KB Output is correct
18 Correct 5 ms 17852 KB Output is correct
19 Correct 6 ms 17756 KB Output is correct
20 Correct 5 ms 18012 KB Output is correct
21 Correct 149 ms 39104 KB Output is correct
22 Correct 56 ms 29340 KB Output is correct
23 Correct 145 ms 36840 KB Output is correct
24 Correct 97 ms 34504 KB Output is correct
25 Correct 653 ms 98308 KB Output is correct
26 Correct 636 ms 88940 KB Output is correct
27 Correct 357 ms 79832 KB Output is correct
28 Correct 440 ms 75056 KB Output is correct
29 Correct 463 ms 74940 KB Output is correct
30 Correct 311 ms 55048 KB Output is correct
31 Correct 120 ms 46464 KB Output is correct
32 Correct 92 ms 31440 KB Output is correct
33 Correct 121 ms 36040 KB Output is correct
34 Correct 350 ms 54464 KB Output is correct
35 Correct 248 ms 49156 KB Output is correct
36 Correct 331 ms 70536 KB Output is correct
37 Correct 408 ms 74868 KB Output is correct
38 Correct 338 ms 78984 KB Output is correct
39 Correct 107 ms 36556 KB Output is correct
40 Correct 438 ms 75088 KB Output is correct
41 Correct 471 ms 74848 KB Output is correct
42 Correct 463 ms 74592 KB Output is correct
43 Correct 144 ms 38744 KB Output is correct
44 Correct 238 ms 41668 KB Output is correct
45 Correct 307 ms 71508 KB Output is correct
46 Correct 285 ms 70724 KB Output is correct
47 Correct 340 ms 74136 KB Output is correct
48 Correct 668 ms 98348 KB Output is correct