Submission #390332

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
390332	2021-04-15T20:44:04 Z	oleksg	Robot (JOI21_ho_t4)	C++11	Compilation error	0 ms	0 KB

Main

#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[100001];
unordered_map<int, ll> cost[100001];
// how much to convert all nodes of a color to some other color

unordered_map<int, ll> dist[100001];
ll dist2[100001];

unordered_map<int, int> used[100001];
//if node with color x was used

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    int one, two, thre
    ll 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++){
            int 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;
            }
        }
        dist2[x] = 1e18;
    }
    priority_queue<tuple<ll, int, int>> q;
    //cost, node, color
    q.push(make_tuple(0, 0, 0));
    dist2[0] = 0;
    while(q.size() > 0){
        int node;
        ll cst;
        int color;
        tie(cst, node, color) = q.top();
        cst *= -1;
        q.pop();
        if (node == n - 1 && color == 0){
            break;
        }
        if (used[node].find(color) == used[node].end()){
            used[node][color] = 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 (dist2[con.d] > ncost){
                                dist2[con.d] = ncost;
                                q.push(make_tuple(-1 * ncost, con.d, 0));
                            }
                        }
                    }
                }
            }
            else{
                //there are 3 things which we can do
                for (auto con: cons[node]){
                    //switch everything but the connection
                    ll ncost = cst + cost[node][con.color] - con.cost;
                    if (dist2[con.d] > ncost){
                        dist2[con.d] = ncost;
                        q.push(make_tuple(-1 * ncost, con.d, 0));
                    }
                    //switch our node only
                    ncost = cst + con.cost;
                    if (dist2[con.d] > ncost){
                        dist2[con.d] = ncost;
                        q.push(make_tuple(-1 * ncost, con.d, 0));
                    }
                    //dont switch anything and make the next node switch
                    ncost = cst;
                    if (dist[con.d].find(con.color) == dist[con.d].end() || (dist[con.d][con.color] > ncost && ncost < dist2[con.d] && cost[con.d][con.color] > con.cost)){
                        dist[con.d][con.color] = ncost;
                        q.push(make_tuple(-1 * ncost, con.d, con.color));
                    }
                }
            }
        }
    }
    if (dist2[n - 1] == 1e18){
        cout << -1 << "\n";
    }
    else{
        cout << dist2[n - 1] << "\n";
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:15:12: error: expected initializer before 'long'
   15 | #define ll long long
      |            ^~~~
Main.cpp:40:5: note: in expansion of macro 'll'
   40 |     ll four;
      |     ^~
Main.cpp:42:30: error: 'three' was not declared in this scope
   42 |         cin >> one >> two >> three >> four;
      |                              ^~~~~
Main.cpp:42:39: error: 'four' was not declared in this scope
   42 |         cin >> one >> two >> three >> four;
      |                                       ^~~~
Main.cpp:43:55: error: no matching function for call to 'std::vector<con>::push_back(<brace-enclosed initializer list>)'
   43 |         cons[one - 1].push_back({two - 1, three, four});
      |                                                       ^
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from Main.cpp:10:
/usr/include/c++/9/bits/stl_vector.h:1184:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = con; _Alloc = std::allocator<con>; std::vector<_Tp, _Alloc>::value_type = con]'
 1184 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:1184:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const con&'}
 1184 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_vector.h:1200:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = con; _Alloc = std::allocator<con>; std::vector<_Tp, _Alloc>::value_type = con]'
 1200 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:1200:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<con>::value_type&&' {aka 'con&&'}
 1200 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
Main.cpp:44:55: error: no matching function for call to 'std::vector<con>::push_back(<brace-enclosed initializer list>)'
   44 |         cons[two - 1].push_back({one - 1, three, four});
      |                                                       ^
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from Main.cpp:10:
/usr/include/c++/9/bits/stl_vector.h:1184:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = con; _Alloc = std::allocator<con>; std::vector<_Tp, _Alloc>::value_type = con]'
 1184 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:1184:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const con&'}
 1184 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_vector.h:1200:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = con; _Alloc = std::allocator<con>; std::vector<_Tp, _Alloc>::value_type = con]'
 1200 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:1200:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<con>::value_type&&' {aka 'con&&'}
 1200 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
Main.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<con>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int y = 0; y < cons[x].size(); y++){
      |                         ~~^~~~~~~~~~~~~~~~