oj.uz

Submission #914179

# Submission time Handle Problem Language Result Execution time Memory
914179 2024-01-21T10:23:57 Z andrei_iorgulescu Robot (JOI21_ho_t4) C++14
100 / 100
 1939 ms 159292 KB 
#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

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.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 4 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 5 ms 10932 KB Output is correct
8 Correct 5 ms 10844 KB Output is correct
9 Correct 8 ms 11868 KB Output is correct
10 Correct 8 ms 11724 KB Output is correct
11 Correct 7 ms 11612 KB Output is correct
12 Correct 7 ms 11612 KB Output is correct
13 Correct 8 ms 11612 KB Output is correct
14 Correct 7 ms 11800 KB Output is correct
15 Correct 6 ms 11096 KB Output is correct
16 Correct 7 ms 11612 KB Output is correct
17 Correct 6 ms 11356 KB Output is correct
18 Correct 4 ms 11100 KB Output is correct
19 Correct 6 ms 11612 KB Output is correct
20 Correct 6 ms 11352 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 54580 KB Output is correct
2 Correct 176 ms 31448 KB Output is correct
3 Correct 476 ms 64104 KB Output is correct
4 Correct 238 ms 40696 KB Output is correct
5 Correct 1912 ms 145276 KB Output is correct
6 Correct 1699 ms 141824 KB Output is correct
7 Correct 1179 ms 131424 KB Output is correct
8 Correct 1434 ms 115408 KB Output is correct
9 Correct 1394 ms 115836 KB Output is correct
10 Correct 946 ms 86272 KB Output is correct
11 Correct 508 ms 69180 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 4 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 3 ms 10588 KB Output is correct
7 Correct 5 ms 10932 KB Output is correct
8 Correct 5 ms 10844 KB Output is correct
9 Correct 8 ms 11868 KB Output is correct
10 Correct 8 ms 11724 KB Output is correct
11 Correct 7 ms 11612 KB Output is correct
12 Correct 7 ms 11612 KB Output is correct
13 Correct 8 ms 11612 KB Output is correct
14 Correct 7 ms 11800 KB Output is correct
15 Correct 6 ms 11096 KB Output is correct
16 Correct 7 ms 11612 KB Output is correct
17 Correct 6 ms 11356 KB Output is correct
18 Correct 4 ms 11100 KB Output is correct
19 Correct 6 ms 11612 KB Output is correct
20 Correct 6 ms 11352 KB Output is correct
21 Correct 429 ms 54580 KB Output is correct
22 Correct 176 ms 31448 KB Output is correct
23 Correct 476 ms 64104 KB Output is correct
24 Correct 238 ms 40696 KB Output is correct
25 Correct 1912 ms 145276 KB Output is correct
26 Correct 1699 ms 141824 KB Output is correct
27 Correct 1179 ms 131424 KB Output is correct
28 Correct 1434 ms 115408 KB Output is correct
29 Correct 1394 ms 115836 KB Output is correct
30 Correct 946 ms 86272 KB Output is correct
31 Correct 508 ms 69180 KB Output is correct
32 Correct 480 ms 80676 KB Output is correct
33 Correct 391 ms 68980 KB Output is correct
34 Correct 926 ms 93420 KB Output is correct
35 Correct 631 ms 79936 KB Output is correct
36 Correct 855 ms 96908 KB Output is correct
37 Correct 1022 ms 111704 KB Output is correct
38 Correct 1221 ms 131348 KB Output is correct
39 Correct 690 ms 96660 KB Output is correct
40 Correct 1421 ms 116804 KB Output is correct
41 Correct 1422 ms 118080 KB Output is correct
42 Correct 1540 ms 126404 KB Output is correct
43 Correct 566 ms 68848 KB Output is correct
44 Correct 942 ms 109676 KB Output is correct
45 Correct 1037 ms 95784 KB Output is correct
46 Correct 919 ms 92856 KB Output is correct
47 Correct 1018 ms 102600 KB Output is correct
48 Correct 1939 ms 159292 KB Output is correct