oj.uz

Submission #390303

# Submission time Handle Problem Language Result Execution time Memory
390303 2021-04-15T19:41:37 Z oleksg Robot (JOI21_ho_t4) C++14
34 / 100
 3000 ms 81764 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();
        q.pop();
        if (used[node].find(color) == used[node].end()){
            used[node][color] = 1;
            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

# Verdict Execution time Memory Grader output
1 Correct 21 ms 33104 KB Output is correct
2 Correct 22 ms 33084 KB Output is correct
3 Correct 20 ms 33072 KB Output is correct
4 Correct 21 ms 33100 KB Output is correct
5 Correct 23 ms 33228 KB Output is correct
6 Correct 21 ms 33100 KB Output is correct
7 Correct 23 ms 33292 KB Output is correct
8 Correct 21 ms 33144 KB Output is correct
9 Correct 27 ms 33860 KB Output is correct
10 Correct 26 ms 33840 KB Output is correct
11 Correct 28 ms 33552 KB Output is correct
12 Correct 28 ms 33632 KB Output is correct
13 Correct 25 ms 33612 KB Output is correct
14 Correct 25 ms 33624 KB Output is correct
15 Correct 24 ms 33548 KB Output is correct
16 Correct 25 ms 33608 KB Output is correct
17 Correct 25 ms 33544 KB Output is correct
18 Correct 22 ms 33228 KB Output is correct
19 Correct 24 ms 33356 KB Output is correct
20 Correct 24 ms 33528 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 55260 KB Output is correct
2 Correct 135 ms 44780 KB Output is correct
3 Correct 324 ms 51996 KB Output is correct
4 Correct 203 ms 48736 KB Output is correct
5 Execution timed out 3073 ms 81764 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 33104 KB Output is correct
2 Correct 22 ms 33084 KB Output is correct
3 Correct 20 ms 33072 KB Output is correct
4 Correct 21 ms 33100 KB Output is correct
5 Correct 23 ms 33228 KB Output is correct
6 Correct 21 ms 33100 KB Output is correct
7 Correct 23 ms 33292 KB Output is correct
8 Correct 21 ms 33144 KB Output is correct
9 Correct 27 ms 33860 KB Output is correct
10 Correct 26 ms 33840 KB Output is correct
11 Correct 28 ms 33552 KB Output is correct
12 Correct 28 ms 33632 KB Output is correct
13 Correct 25 ms 33612 KB Output is correct
14 Correct 25 ms 33624 KB Output is correct
15 Correct 24 ms 33548 KB Output is correct
16 Correct 25 ms 33608 KB Output is correct
17 Correct 25 ms 33544 KB Output is correct
18 Correct 22 ms 33228 KB Output is correct
19 Correct 24 ms 33356 KB Output is correct
20 Correct 24 ms 33528 KB Output is correct
21 Correct 287 ms 55260 KB Output is correct
22 Correct 135 ms 44780 KB Output is correct
23 Correct 324 ms 51996 KB Output is correct
24 Correct 203 ms 48736 KB Output is correct
25 Execution timed out 3073 ms 81764 KB Time limit exceeded
26 Halted 0 ms 0 KB -