oj.uz

Submission #915772

# Submission time Handle Problem Language Result Execution time Memory
915772 2024-01-24T17:01:24 Z ace5 Robot (JOI21_ho_t4) C++17
24 / 100
 957 ms 75152 KB 
#include <bits/stdc++.h>

using namespace std;

#define int int64_t

const int INF = 1e18;

struct edge
{
    edge(int _v,int _to,int _c,int _p){v = _v;to = _to;c = _c;p = _p;};
    edge(){v = 0;to = 0;c = 0;p = 0;};
    int v;
    int to;
    int c;
    int p;
};

vector<vector<int>> g;
vector<map<int,vector<int>>> rc;
vector<map<int,int>> sum;
vector<edge> e;
vector<int> dist;
vector<int> vis;
set<pair<int,int>> ff;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    g.resize(n);
    rc.resize(n);
    sum.resize(n);
    for(int j = 0;j < m;++j)
    {
        int u,v,c,p;
        cin >> u >> v >> c >> p;
        u--;
        v--;
        e.push_back(edge(u,v,c,p));
        g[u].push_back(j);
        g[v].push_back(j);
        sum[u][c] += p;
        sum[v][c] += p;
        rc[u][c].push_back(j);
        rc[v][c].push_back(j);
    }
    dist.resize(n);
    vis.resize(n);
    for(int j =0 ;j < n;++j)
    {
        dist[j] = INF;
        vis[j] = 0;
    }
    dist[0] =0;
    ff.insert({0,0});
    while(ff.size())
    {
        int v = (*ff.begin()).second;
        ff.erase(ff.begin());
        vis[v] = 1;
        for(auto ind:g[v])
        {
            int u = e[ind].v + e[ind].to - v;
            int64_t nu = dist[v] + min(e[ind].p,sum[v][e[ind].c]-e[ind].p);
            if(!vis[u] && dist[u] > nu)
            {
                ff.erase({dist[u],u});
                dist[u] = nu;
                ff.insert({dist[u],u});
            }
            if(rc[u][e[ind].c].size() == 2)
            {
                int ind2 = (rc[u][e[ind].c][0]+rc[u][e[ind].c][1]-ind);
                int64_t v2 = e[ind2].v+e[ind2].to-u;
                if(!vis[v2] && dist[v2] > dist[v] + e[ind].p)
                {
                    ff.erase({dist[v2],v2});
                    dist[v2] = dist[v] + e[ind].p;
                    ff.insert({dist[v2],v2});
                }
            }
        }
    }
    cout << (dist[n-1] == INF ? -1 : dist[n-1]);
    return 0;
}

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 2 ms 984 KB Output is correct
12 Incorrect 2 ms 860 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 22836 KB Output is correct
2 Correct 37 ms 11972 KB Output is correct
3 Correct 134 ms 26056 KB Output is correct
4 Correct 62 ms 16572 KB Output is correct
5 Correct 957 ms 75152 KB Output is correct
6 Correct 735 ms 67564 KB Output is correct
7 Correct 346 ms 54716 KB Output is correct
8 Correct 369 ms 53144 KB Output is correct
9 Correct 352 ms 52148 KB Output is correct
10 Correct 277 ms 40236 KB Output is correct
11 Correct 127 ms 33524 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 2 ms 984 KB Output is correct
12 Incorrect 2 ms 860 KB Output isn't correct
13 Halted 0 ms 0 KB -