oj.uz

답안 #640067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
640067 2022-09-13T13:00:26 Z victor_gao Robot (JOI21_ho_t4) C++17
100 / 100
 1048 ms 105640 KB 
#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,m;
struct Edge{
    int to,col,cost;
    Edge(int a,int b,int c):to(a),cost(b),col(c){}
};
map<int,int>dis[N],all[N];
vector<Edge>g[N];
map<int,vector<pii> >ng[N];
signed main(){
    fast
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int a,b,c,d; cin>>a>>b>>c>>d;
        g[a].push_back(Edge(b,d,c));
        g[b].push_back(Edge(a,d,c));
        ng[a][c].push_back({b,d});
        ng[b][c].push_back({a,d});
        all[a][c]+=d;
        all[b][c]+=d;
    }
    dis[1][0]=0;
    priority_queue<pair<int,pii>,vector<pair<int,pii> >,greater<pair<int,pii> > >pq;
    pq.push({0,{1,0}});
    while (!pq.empty()){
        auto np=pq.top(); pq.pop();
        if (dis[np.y.x][np.y.y]!=np.x) continue;
        if (np.y.y){
            for (auto i:ng[np.y.x][np.y.y]){
                int new_cost=all[np.y.x][np.y.y]-i.y;
                if (!dis[i.x].count(0)||dis[i.x][0]>np.x+new_cost){
                    dis[i.x][0]=np.x+new_cost;
                    pq.push({np.x+new_cost,{i.x,0}});
                }
            }
        }
        else {
            for (auto i:g[np.y.x]){
                int new_cost=min(all[np.y.x][i.col]-i.cost,i.cost);
                if (!dis[i.to].count(0)||dis[i.to][0]>np.x+new_cost){
                    dis[i.to][0]=np.x+new_cost;
                    pq.push({np.x+new_cost,{i.to,0}});
                }
                new_cost=0;
                if (!dis[i.to].count(i.col)||dis[i.to][i.col]>np.x+new_cost){
                    dis[i.to][i.col]=np.x+new_cost;
                    pq.push({np.x+new_cost,{i.to,i.col}});
                }
            }
        }
    }
    if (!dis[n].count(0)) cout<<-1<<'\n';
    else cout<<dis[n][0]<<'\n';
}

Compilation message

Main.cpp: In constructor 'Edge::Edge(long long int, long long int, long long int)':
Main.cpp:19:16: warning: 'Edge::cost' will be initialized after [-Wreorder]
   19 |     int to,col,cost;
      |                ^~~~
Main.cpp:19:12: warning:   'long long int Edge::col' [-Wreorder]
   19 |     int to,col,cost;
      |            ^~~
Main.cpp:20:5: warning:   when initialized here [-Wreorder]
   20 |     Edge(int a,int b,int c):to(a),cost(b),col(c){}
      |     ^~~~

Subtask #1
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 9 ms 16672 KB Output is correct
3 Correct 10 ms 16724 KB Output is correct
4 Correct 11 ms 16724 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 9 ms 16980 KB Output is correct
8 Correct 9 ms 16852 KB Output is correct
9 Correct 13 ms 17560 KB Output is correct
10 Correct 12 ms 17528 KB Output is correct
11 Correct 11 ms 17216 KB Output is correct
12 Correct 11 ms 17236 KB Output is correct
13 Correct 10 ms 17308 KB Output is correct
14 Correct 12 ms 17304 KB Output is correct
15 Correct 11 ms 17164 KB Output is correct
16 Correct 11 ms 17236 KB Output is correct
17 Correct 11 ms 17236 KB Output is correct
18 Correct 10 ms 16976 KB Output is correct
19 Correct 11 ms 17108 KB Output is correct
20 Correct 10 ms 17108 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 214 ms 42480 KB Output is correct
2 Correct 91 ms 29764 KB Output is correct
3 Correct 228 ms 42020 KB Output is correct
4 Correct 132 ms 34224 KB Output is correct
5 Correct 1048 ms 100060 KB Output is correct
6 Correct 826 ms 89044 KB Output is correct
7 Correct 350 ms 69964 KB Output is correct
8 Correct 479 ms 68376 KB Output is correct
9 Correct 515 ms 68484 KB Output is correct
10 Correct 372 ms 58360 KB Output is correct
11 Correct 160 ms 39136 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 9 ms 16672 KB Output is correct
3 Correct 10 ms 16724 KB Output is correct
4 Correct 11 ms 16724 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 9 ms 16980 KB Output is correct
8 Correct 9 ms 16852 KB Output is correct
9 Correct 13 ms 17560 KB Output is correct
10 Correct 12 ms 17528 KB Output is correct
11 Correct 11 ms 17216 KB Output is correct
12 Correct 11 ms 17236 KB Output is correct
13 Correct 10 ms 17308 KB Output is correct
14 Correct 12 ms 17304 KB Output is correct
15 Correct 11 ms 17164 KB Output is correct
16 Correct 11 ms 17236 KB Output is correct
17 Correct 11 ms 17236 KB Output is correct
18 Correct 10 ms 16976 KB Output is correct
19 Correct 11 ms 17108 KB Output is correct
20 Correct 10 ms 17108 KB Output is correct
21 Correct 214 ms 42480 KB Output is correct
22 Correct 91 ms 29764 KB Output is correct
23 Correct 228 ms 42020 KB Output is correct
24 Correct 132 ms 34224 KB Output is correct
25 Correct 1048 ms 100060 KB Output is correct
26 Correct 826 ms 89044 KB Output is correct
27 Correct 350 ms 69964 KB Output is correct
28 Correct 479 ms 68376 KB Output is correct
29 Correct 515 ms 68484 KB Output is correct
30 Correct 372 ms 58360 KB Output is correct
31 Correct 160 ms 39136 KB Output is correct
32 Correct 143 ms 37528 KB Output is correct
33 Correct 191 ms 38668 KB Output is correct
34 Correct 442 ms 61108 KB Output is correct
35 Correct 335 ms 51460 KB Output is correct
36 Correct 330 ms 59892 KB Output is correct
37 Correct 378 ms 65116 KB Output is correct
38 Correct 386 ms 76380 KB Output is correct
39 Correct 159 ms 43872 KB Output is correct
40 Correct 510 ms 68432 KB Output is correct
41 Correct 520 ms 68660 KB Output is correct
42 Correct 575 ms 74756 KB Output is correct
43 Correct 226 ms 44196 KB Output is correct
44 Correct 447 ms 55544 KB Output is correct
45 Correct 382 ms 62068 KB Output is correct
46 Correct 336 ms 61640 KB Output is correct
47 Correct 342 ms 63228 KB Output is correct
48 Correct 1030 ms 105640 KB Output is correct