oj.uz

Submission #1078950

# Submission time Handle Problem Language Result Execution time Memory
1078950 2024-08-28T08:34:26 Z _rain_ Robot (JOI21_ho_t4) C++14
100 / 100
 371 ms 132820 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fixbug true

void SETIO(string name = ""){
    if (name=="") return;
    freopen((name+".inp").c_str(),"r",stdin);
//    freopen((name+".out").c_str(),"w",stdout);
    return;
}

const int maxn = 7e5;
const int maxm = 2e5;
struct Node{
    int to , c , p;
    Node(int to , int c , int p) : to(to) , c(c) , p(p) {};
};
int n , m;
vector<Node> g[maxn+2];
vector<pair<int,ll>> graph[maxn+2];
#define fi first
#define se second
bool used[maxm+2] , vis[maxn+2];
int tot = 0;
ll sum[maxm+2] , d[maxn+2];
void add_edge(int u , int v , ll cost){
    graph[u].push_back({v , cost});
    return;
}
map<int,int> vert[maxn+2];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    SETIO("");

    cin >> n >> m;
    for (int i = 1 ; i <= m; ++i){
        int u , v , c , p; cin >> u >> v >> c >> p;
        g[u].push_back(Node(v,c,p));
        g[v].push_back(Node(u,c,p));
    }
    tot = n;
    for (int i = 1; i <= n; ++i){
        for (auto& x : g[i]){
            if (!used[x.c])
                vert[i][x.c] = ++tot;
            used[x.c] = true;
        }
        for (auto& x : g[i]) used[x.c] = false;
    }
    for (int u = 1; u <= n; ++u){
        for (auto& x : g[u]) sum[x.c] += x.p;
        for (auto& x : g[u]){
            int v = x.to , c = x.c , p = x.p;
            add_edge(u , v , min((ll)p , sum[c] - p));
            add_edge(u , vert[v][c] , 0);
            add_edge(vert[u][c] , v , sum[c] - p);
        }
        for (auto& x : g[u]) sum[x.c] = 0;
    }
    memset(d,0x3f,sizeof d);
    ll INF = d[0];
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
    q.push({0 , 1});
    while (q.size()){
        ll cost = q.top().first;
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        d[u] = cost; vis[u] = true;
        for (auto& v : graph[u]){
            if (!vis[v.first]){
                q.push({cost + v.second , v.first});
            }
        }
    }
    cout << (d[n] == INF ? -1 : d[n]);
}

Compilation message

Main.cpp: In function 'void SETIO(std::string)':
Main.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen((name+".inp").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 71516 KB Output is correct
2 Correct 29 ms 71504 KB Output is correct
3 Correct 29 ms 71516 KB Output is correct
4 Correct 29 ms 71588 KB Output is correct
5 Correct 30 ms 71508 KB Output is correct
6 Correct 35 ms 71508 KB Output is correct
7 Correct 35 ms 71932 KB Output is correct
8 Correct 33 ms 71764 KB Output is correct
9 Correct 31 ms 72276 KB Output is correct
10 Correct 32 ms 72020 KB Output is correct
11 Correct 31 ms 72020 KB Output is correct
12 Correct 32 ms 72016 KB Output is correct
13 Correct 32 ms 72020 KB Output is correct
14 Correct 33 ms 72028 KB Output is correct
15 Correct 32 ms 71764 KB Output is correct
16 Correct 39 ms 72016 KB Output is correct
17 Correct 31 ms 72020 KB Output is correct
18 Correct 32 ms 71772 KB Output is correct
19 Correct 34 ms 72284 KB Output is correct
20 Correct 31 ms 72028 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 94416 KB Output is correct
2 Correct 68 ms 81104 KB Output is correct
3 Correct 166 ms 107284 KB Output is correct
4 Correct 89 ms 85968 KB Output is correct
5 Correct 346 ms 127344 KB Output is correct
6 Correct 301 ms 122572 KB Output is correct
7 Correct 189 ms 116524 KB Output is correct
8 Correct 237 ms 115328 KB Output is correct
9 Correct 264 ms 115024 KB Output is correct
10 Correct 200 ms 105164 KB Output is correct
11 Correct 103 ms 93776 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 71516 KB Output is correct
2 Correct 29 ms 71504 KB Output is correct
3 Correct 29 ms 71516 KB Output is correct
4 Correct 29 ms 71588 KB Output is correct
5 Correct 30 ms 71508 KB Output is correct
6 Correct 35 ms 71508 KB Output is correct
7 Correct 35 ms 71932 KB Output is correct
8 Correct 33 ms 71764 KB Output is correct
9 Correct 31 ms 72276 KB Output is correct
10 Correct 32 ms 72020 KB Output is correct
11 Correct 31 ms 72020 KB Output is correct
12 Correct 32 ms 72016 KB Output is correct
13 Correct 32 ms 72020 KB Output is correct
14 Correct 33 ms 72028 KB Output is correct
15 Correct 32 ms 71764 KB Output is correct
16 Correct 39 ms 72016 KB Output is correct
17 Correct 31 ms 72020 KB Output is correct
18 Correct 32 ms 71772 KB Output is correct
19 Correct 34 ms 72284 KB Output is correct
20 Correct 31 ms 72028 KB Output is correct
21 Correct 129 ms 94416 KB Output is correct
22 Correct 68 ms 81104 KB Output is correct
23 Correct 166 ms 107284 KB Output is correct
24 Correct 89 ms 85968 KB Output is correct
25 Correct 346 ms 127344 KB Output is correct
26 Correct 301 ms 122572 KB Output is correct
27 Correct 189 ms 116524 KB Output is correct
28 Correct 237 ms 115328 KB Output is correct
29 Correct 264 ms 115024 KB Output is correct
30 Correct 200 ms 105164 KB Output is correct
31 Correct 103 ms 93776 KB Output is correct
32 Correct 158 ms 108064 KB Output is correct
33 Correct 145 ms 103108 KB Output is correct
34 Correct 232 ms 109304 KB Output is correct
35 Correct 169 ms 102408 KB Output is correct
36 Correct 163 ms 100164 KB Output is correct
37 Correct 193 ms 112032 KB Output is correct
38 Correct 196 ms 116516 KB Output is correct
39 Correct 181 ms 116160 KB Output is correct
40 Correct 267 ms 116836 KB Output is correct
41 Correct 254 ms 116820 KB Output is correct
42 Correct 262 ms 118852 KB Output is correct
43 Correct 139 ms 96708 KB Output is correct
44 Correct 242 ms 123324 KB Output is correct
45 Correct 194 ms 106576 KB Output is correct
46 Correct 159 ms 104536 KB Output is correct
47 Correct 193 ms 105728 KB Output is correct
48 Correct 371 ms 132820 KB Output is correct