oj.uz

답안 #390301

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
390301 2021-04-15T19:39:52 Z oleksg Robot (JOI21_ho_t4) C++14
34 / 100
 3000 ms 81404 KB 
#pragma GCC optimize("O2")
#include <fstream>
#include <string>
#include <iostream>
#include <bitset>
#include <math.h>
#include <string>
#include <algorithm>
#include <assert.h>
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include<stdio.h>
#include<ctype.h>
#define ll long long
using namespace std;


ll n, m;
struct con{
    ll d;
    ll color;
    ll cost;
};

vector<con> cons[200001];
map<ll, ll> cost[200001];
// how much to convert all nodes of a color to some other color

map<ll, ll> dist[200001];

map<ll, ll> used[200001];
//if node with color x was used

int main(){
    cin >> n >> m;
    ll one, two, three, four;
    for (int x = 0; x < m; x++){
        cin >> one >> two >> three >> four;
        cons[one - 1].push_back({two - 1, three, four});
        cons[two - 1].push_back({one - 1, three, four});
    }
    for (int x = 0; x < n; x++){
        for (int y = 0; y < cons[x].size(); y++){
            ll col = cons[x][y].color;
            ll cst = cons[x][y].cost;
            if (cost[x].find(col) == cost[x].end()){
                cost[x][col] = cst;
            } else {
                cost[x][col] += cst;
            }
        }
    }
    priority_queue<tuple<ll, ll, ll>> q;
    //cost, node, color
    q.push(make_tuple(0, 0, 0));
    while(q.size() > 0){
        ll node;
        ll cst;
        ll color;
        tie(cst, node, color) = q.top();
        used[node][color] = 1;
        q.pop();
        cst *= -1;
        if (color != 0){
            //we need to go to a node with the same color
            for (auto con: cons[node]){
                if (con.color == color){
                    if (used[con.d].find(0) == used[con.d].end()){
                        ll ncost = cst + cost[node][color] - con.cost;
                        if (dist[con.d].find(0) == dist[con.d].end() || dist[con.d][0] > ncost){
                            dist[con.d][0] = ncost;
                            q.push(make_tuple(-1 * ncost, con.d, 0));
                        }
                    }
                }
            }
        }
        else{
            //there are 3 things which we can do
            for (auto con: cons[node]){
                if (used[con.d].find(con.color) == used[con.d].end()){
                    //dont switch anything and make the next node switch
                    ll ncost = cst;
                    if (dist[con.d].find(con.color) == dist[con.d].end() || dist[con.d][con.color] > ncost){
                        dist[con.d][con.color] = ncost;
                        q.push(make_tuple(-1 * ncost, con.d, con.color));
                    }
                }
                if (used[con.d].find(0) == used[con.d].end()){
                    //switch everything but the connection
                    ll ncost = cst + cost[node][con.color] - con.cost;
                    if (dist[con.d].find(0) == dist[con.d].end() || dist[con.d][0] > ncost){
                        dist[con.d][0] = ncost;
                        q.push(make_tuple(-1 * ncost, con.d, 0));
                    }
                    //switch our node only
                    ncost = cst + con.cost;
                    if (dist[con.d].find(0) == dist[con.d].end() || dist[con.d][0] > ncost){
                        dist[con.d][0] = ncost;
                        q.push(make_tuple(-1 * ncost, con.d, 0));
                    }
                }
            }
        }
    }
    if (dist[n - 1].find(0) == dist[n - 1].end()){
        cout << -1 << "\n";
    }
    else{
        cout << dist[n - 1][0] << "\n";
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<con>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int y = 0; y < cons[x].size(); y++){
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 33100 KB Output is correct
2 Correct 21 ms 33176 KB Output is correct
3 Correct 21 ms 33172 KB Output is correct
4 Correct 21 ms 33108 KB Output is correct
5 Correct 21 ms 33100 KB Output is correct
6 Correct 21 ms 33100 KB Output is correct
7 Correct 22 ms 33324 KB Output is correct
8 Correct 21 ms 33220 KB Output is correct
9 Correct 26 ms 33868 KB Output is correct
10 Correct 26 ms 33848 KB Output is correct
11 Correct 25 ms 33612 KB Output is correct
12 Correct 23 ms 33564 KB Output is correct
13 Correct 25 ms 33612 KB Output is correct
14 Correct 24 ms 33616 KB Output is correct
15 Correct 23 ms 33576 KB Output is correct
16 Correct 25 ms 33564 KB Output is correct
17 Correct 25 ms 33624 KB Output is correct
18 Correct 22 ms 33228 KB Output is correct
19 Correct 25 ms 33444 KB Output is correct
20 Correct 24 ms 33484 KB Output is correct

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 318 ms 56864 KB Output is correct
2 Correct 151 ms 45308 KB Output is correct
3 Correct 340 ms 54476 KB Output is correct
4 Correct 203 ms 49652 KB Output is correct
5 Execution timed out 3072 ms 81404 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 33100 KB Output is correct
2 Correct 21 ms 33176 KB Output is correct
3 Correct 21 ms 33172 KB Output is correct
4 Correct 21 ms 33108 KB Output is correct
5 Correct 21 ms 33100 KB Output is correct
6 Correct 21 ms 33100 KB Output is correct
7 Correct 22 ms 33324 KB Output is correct
8 Correct 21 ms 33220 KB Output is correct
9 Correct 26 ms 33868 KB Output is correct
10 Correct 26 ms 33848 KB Output is correct
11 Correct 25 ms 33612 KB Output is correct
12 Correct 23 ms 33564 KB Output is correct
13 Correct 25 ms 33612 KB Output is correct
14 Correct 24 ms 33616 KB Output is correct
15 Correct 23 ms 33576 KB Output is correct
16 Correct 25 ms 33564 KB Output is correct
17 Correct 25 ms 33624 KB Output is correct
18 Correct 22 ms 33228 KB Output is correct
19 Correct 25 ms 33444 KB Output is correct
20 Correct 24 ms 33484 KB Output is correct
21 Correct 318 ms 56864 KB Output is correct
22 Correct 151 ms 45308 KB Output is correct
23 Correct 340 ms 54476 KB Output is correct
24 Correct 203 ms 49652 KB Output is correct
25 Execution timed out 3072 ms 81404 KB Time limit exceeded
26 Halted 0 ms 0 KB -