oj.uz

Submission #1078938

# Submission time Handle Problem Language Result Execution time Memory
1078938 2024-08-28T08:24:33 Z _rain_ Robot (JOI21_ho_t4) C++14
0 / 100
 202 ms 61840 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 = 1e5;
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,int>> graph[maxn+2];
#define fi first
#define se second
bool used[maxm+2] , vis[maxn+2];
int tot = 0;
ll sum[maxm+2];
ll d[maxn+2];
void add_edge(int u , int v , int 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
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10588 KB Output is correct
2 Correct 4 ms 10588 KB Output is correct
3 Correct 4 ms 10840 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Correct 4 ms 10588 KB Output is correct
6 Incorrect 4 ms 10588 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 28808 KB Output is correct
2 Correct 47 ms 18388 KB Output is correct
3 Correct 202 ms 37308 KB Output is correct
4 Correct 95 ms 21964 KB Output is correct
5 Runtime error 121 ms 61840 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10588 KB Output is correct
2 Correct 4 ms 10588 KB Output is correct
3 Correct 4 ms 10840 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Correct 4 ms 10588 KB Output is correct
6 Incorrect 4 ms 10588 KB Output isn't correct
7 Halted 0 ms 0 KB -