Submission #914179

#	Time	Username	Problem	Language	Result	Execution time	Memory
914179		andrei_iorgulescu	Robot (JOI21_ho_t4)	C++14	100 / 100	1939 ms	159292 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using namespace chrono;

using ll = long long;

ll inf = 1e18;
ll infmic = 1e9;

struct ura
{
    int x,y,culoare,pret;
};

ll fall(ll x,ll y)
{
    return infmic * x + y;
}

vector<ura>muchii;
int n,m;
unordered_map<ll,int>cul,cost;
unordered_set<int>culori[100005];
vector<ll>d[100005];
vector<vector<pair<pair<int,int>,ll>>>g[100005];
unordered_map<ll,int>idkmap;
unordered_map<ll,ll>sumcost;

void putedge(int x,int y)
{
    //cout << x << ' ' << y << endl;
    //int c = cul[{x,y}];
    //int pret = cost[{x,y}];
    int c = cul[fall(x,y)];
    int pret = cost[fall(x,y)];
    ///(x,0) -> (y,0)
    ll cost1 = pret;
    //ll cost2 = sumcost[{x,c}] - cost1;
    ll cost2 = sumcost[fall(x,c)] - cost1;
    ll act_cost = min(cost1,cost2);
    g[x][0].push_back({{y,0},act_cost});
    //cout << "1" << endl;
    ///(x,0) -> (y,c)
    //g[x][0].push_back({{y,idkmap[{y,c}]},0});
    g[x][0].push_back({{y,idkmap[fall(y,c)]},0});
    //cout << "2" << endl;
    ///(x,c) -> (y,0)
    //act_cost = sumcost[{x,c}] - cost1;
    act_cost = sumcost[fall(x,c)] - cost1;
    //g[x][idkmap[{x,c}]].push_back({{y,0},act_cost});
    g[x][idkmap[fall(x,c)]].push_back({{y,0},act_cost});
    //cout << "3" << endl;
}

signed main()
{
    auto primul_moment = high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x,y,culoare,pret;
        cin >> x >> y >> culoare >> pret;
        //sumcost[{x,culoare}] += pret;
        //sumcost[{y,culoare}] += pret;
        sumcost[fall(x,culoare)] += pret;
        sumcost[fall(y,culoare)] += pret;
        ura aux;
        aux.x = x;
        aux.y = y;
        aux.culoare = culoare;
        aux.pret = pret;
        muchii.push_back(aux);
        //cul[{x,y}] = cul[{y,x}] = culoare;
        //cost[{x,y}] = cost[{y,x}] = pret;
        cul[fall(x,y)] = cul[fall(y,x)] = culoare;
        cost[fall(x,y)] = cost[fall(y,x)] = pret;
        culori[x].insert(culoare);
        culori[y].insert(culoare);
    }
    for (int i = 1; i <= n; i++)
    {
        d[i].resize(culori[i].size() + 1);
        for (int j = 0; j <= culori[i].size(); j++)
            d[i][j] = inf;
        g[i].resize(culori[i].size() + 1);
        int jjj = 0;
        for (auto it : culori[i])
        {
            jjj++;
            //idkmap[{i,it}] = jjj;
            idkmap[fall(i,it)] = jjj;
        }
    }
    auto al_doilea_moment = high_resolution_clock::now();
    auto cat_a_durat = duration_cast<milliseconds>(al_doilea_moment - primul_moment);
    for (auto it : muchii)
    {
        putedge(it.x,it.y);
        putedge(it.y,it.x);
    }
    //if (cat_a_durat.count() >= 1500)
      //  assert(false);
    priority_queue<pair<ll,pair<int,int>>>pq;
    pq.push({0,{1,0}});
    while (!pq.empty())
    {
        pair<int,int>nod = pq.top().second;
        ll timp = -pq.top().first;
        pq.pop();
        if (d[nod.first][nod.second] == inf)
        {
            d[nod.first][nod.second] = timp;
            if (nod.first == n and nod.second == 0)
                break;
            for (auto vecin : g[nod.first][nod.second])
            {
                pair<ll,pair<int,int>>de_bagat;
                de_bagat.first = -(timp + vecin.second);
                de_bagat.second = vecin.first;
                pq.push(de_bagat);
            }
        }
    }
    if (d[n][0] == inf)
        cout << -1;
    else
        cout << d[n][0];
    return 0;
}

/**
Stari: {nod,-1}, {nod,cul}, [nod,cul]
le definesc prin pereche (nod,-1 sau ceva intre 1 si m sau ceva intre 1 si 2m)
pentru nod, pot avea (nod,-1), (nod,c din culori[nod]) sau (nod, m + c din culori[nod])

Tranzitii:
(nod,-1) -> (vecin,-1) cost = min(toate muchiile adiacente cu nod de culoarea cul[{nod,vecin}] mai putin fix muchia {nod,vecin}, cost[{nod,vecin}])
(nod,-1) -> (vecin, cul[{nod,vecin}]) de cost 0
(nod,c) -> (vecin,-1) de cost toate muchiile adiacente cu nod de culoarea c mai putin fix muchia {nod,vecin}, conditie: cul[{nod,vecin}] = c

initial (1,-1) = 0
raspunsul este (n,-1)
**/

/**
graful asta are n + 2m noduri cel mult
(nod,c) pot sa pp ca are doar muchii de culoarea c
atunci numarul de muchii este 2m + 2m + 2m = 6m muchii
pe care dau un dijksta finut, iese N = n + 2m si M = 6m, iese MlogM + N
**/

/**
cum tin graful?
pai am o matrice de stari
la o linie am asa:
(nod,0) reprezinta (nod,-1)
(nod,1),(nod,2),...,(nod,k[nod]) reprezinta culorile din nod
**/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int j = 0; j <= culori[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42