oj.uz

답안 #638065

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
638065 2022-09-04T13:54:54 Z chjiao Robot (JOI21_ho_t4) C++17
100 / 100
 781 ms 85088 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define newl '\n'
const int mod = 1e9+7;
const ll MAX = 0x3f3f3f3f3f3f3f3f;
const int MN = 1e5+1;// 1e5;
vector<ll> dp(MN, MAX);
vector<map<int,ll>> dp2(MN);
vector<map<int,ll>> colorsum(MN);  //elemnent, color, sum 
vector<map<int,vector<pair<int,ll>>>> neighbors(MN); //element, map<bridge color> , element, bridge lenghth
struct quadriple{
    ll value;
    int curr;
    //bool changed;
    int roadcolor;
    // int roadvalue;
};
struct cmp {
    bool operator ()(quadriple & a, quadriple& b){
        return a.value > b.value;
    }
};
void dijkstra(int s) {
    priority_queue<quadriple, vector<quadriple>, cmp> pq;
    dp[0] = 0;
    pq.push({0,0,0});

    while(!pq.empty()){
        quadriple c = pq.top();
        pq.pop();
        //case 1, if color changed

        if(c.roadcolor!= 0){
            if(dp2[c.curr][c.roadcolor] == c.value){
                for(auto [element, value]: neighbors[c.curr][c.roadcolor]){
                    ll case1 = colorsum[c.curr][c.roadcolor] -value+c.value;
                    if(dp[element] > case1){
                        dp[element] = case1;
                        pq.push({case1, element, 0});
                    }
                }
            }
            

        }else if(dp[c.curr] == c.value){        //cases 2, if color hasn't changed
            for(auto &[color,v]: neighbors[c.curr]){
                for(auto &[element, value]: v){
                    //cases 2.1 change myself
                    ll newcase = c.value +value;
                    if(newcase<dp[element]){
                        dp[element] = newcase;
                        pq.push({newcase, element, 0});
                    }
                
                    //cases 2.2 change other
                    newcase =  colorsum[c.curr][color]+ c.value- value;
                    if(newcase< dp[element]){
                        dp[element] = newcase;
                        pq.push({newcase, element , 0});
                    }

                    //cases 2.3 When changing i, affects i+2
                    newcase = c.value;
                    if(!dp2[element].count(color) ||dp2[element][color] > newcase ){
                        dp2[element][color] = newcase;
                        pq.push({newcase, element, color});
                    }
                }


                        
            }
        }
        
        //cases 2, if color hasn't changed
        //cases 2.1 change myself
        //cases 2.2 change other
        //cases 2.3 When changing i, affects i+2
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("Robot.in", "r", stdin);
    //freopen("nocross.out", "w", stdout); 
    int N,M,a,b,c,d;
    cin >> N >> M;
    
    for(int i=0; i<M; i++){
        cin >> a >> b >> c >> d;
        a--;
        b--;
        neighbors[a][c].push_back(make_pair(b,d));
        neighbors[b][c].push_back(make_pair(a,d));
        colorsum[a][c] +=d;
        colorsum[b][c] +=d;

    }

    dijkstra(0);
    if(dp[N-1] == MAX){
        cout << -1 << endl;
        return 0;
    }
    cout << dp[N-1] << endl;
}

Subtask #1
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15188 KB Output is correct
2 Correct 8 ms 15188 KB Output is correct
3 Correct 9 ms 15188 KB Output is correct
4 Correct 8 ms 15188 KB Output is correct
5 Correct 9 ms 15188 KB Output is correct
6 Correct 8 ms 15188 KB Output is correct
7 Correct 9 ms 15316 KB Output is correct
8 Correct 8 ms 15188 KB Output is correct
9 Correct 11 ms 15828 KB Output is correct
10 Correct 10 ms 15700 KB Output is correct
11 Correct 8 ms 15496 KB Output is correct
12 Correct 10 ms 15444 KB Output is correct
13 Correct 9 ms 15444 KB Output is correct
14 Correct 8 ms 15444 KB Output is correct
15 Correct 9 ms 15388 KB Output is correct
16 Correct 10 ms 15512 KB Output is correct
17 Correct 9 ms 15444 KB Output is correct
18 Correct 8 ms 15316 KB Output is correct
19 Correct 10 ms 15444 KB Output is correct
20 Correct 9 ms 15444 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 34828 KB Output is correct
2 Correct 66 ms 25184 KB Output is correct
3 Correct 175 ms 32100 KB Output is correct
4 Correct 105 ms 28256 KB Output is correct
5 Correct 781 ms 83408 KB Output is correct
6 Correct 568 ms 71756 KB Output is correct
7 Correct 271 ms 52008 KB Output is correct
8 Correct 341 ms 50784 KB Output is correct
9 Correct 345 ms 50924 KB Output is correct
10 Correct 274 ms 48044 KB Output is correct
11 Correct 118 ms 32824 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15188 KB Output is correct
2 Correct 8 ms 15188 KB Output is correct
3 Correct 9 ms 15188 KB Output is correct
4 Correct 8 ms 15188 KB Output is correct
5 Correct 9 ms 15188 KB Output is correct
6 Correct 8 ms 15188 KB Output is correct
7 Correct 9 ms 15316 KB Output is correct
8 Correct 8 ms 15188 KB Output is correct
9 Correct 11 ms 15828 KB Output is correct
10 Correct 10 ms 15700 KB Output is correct
11 Correct 8 ms 15496 KB Output is correct
12 Correct 10 ms 15444 KB Output is correct
13 Correct 9 ms 15444 KB Output is correct
14 Correct 8 ms 15444 KB Output is correct
15 Correct 9 ms 15388 KB Output is correct
16 Correct 10 ms 15512 KB Output is correct
17 Correct 9 ms 15444 KB Output is correct
18 Correct 8 ms 15316 KB Output is correct
19 Correct 10 ms 15444 KB Output is correct
20 Correct 9 ms 15444 KB Output is correct
21 Correct 169 ms 34828 KB Output is correct
22 Correct 66 ms 25184 KB Output is correct
23 Correct 175 ms 32100 KB Output is correct
24 Correct 105 ms 28256 KB Output is correct
25 Correct 781 ms 83408 KB Output is correct
26 Correct 568 ms 71756 KB Output is correct
27 Correct 271 ms 52008 KB Output is correct
28 Correct 341 ms 50784 KB Output is correct
29 Correct 345 ms 50924 KB Output is correct
30 Correct 274 ms 48044 KB Output is correct
31 Correct 118 ms 32824 KB Output is correct
32 Correct 122 ms 29064 KB Output is correct
33 Correct 141 ms 29916 KB Output is correct
34 Correct 341 ms 50440 KB Output is correct
35 Correct 280 ms 41672 KB Output is correct
36 Correct 253 ms 46396 KB Output is correct
37 Correct 275 ms 48808 KB Output is correct
38 Correct 290 ms 55636 KB Output is correct
39 Correct 159 ms 32468 KB Output is correct
40 Correct 377 ms 52196 KB Output is correct
41 Correct 414 ms 52428 KB Output is correct
42 Correct 473 ms 60688 KB Output is correct
43 Correct 189 ms 37480 KB Output is correct
44 Correct 431 ms 43356 KB Output is correct
45 Correct 270 ms 47564 KB Output is correct
46 Correct 237 ms 47912 KB Output is correct
47 Correct 282 ms 48352 KB Output is correct
48 Correct 731 ms 85088 KB Output is correct