oj.uz

Submission #806613

# Submission time Handle Problem Language Result Execution time Memory
806613 2023-08-04T08:19:46 Z vjudge1 Robot (JOI21_ho_t4) C++17
0 / 100
 810 ms 45812 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 10;
const int M = 2e5 + 10;
const ll INF = 1e16;
int n, m;


int C[M], P[M];
struct edge {
    int to, i;
};
struct state {
    int v, st, ix, color;
};
bool operator < (state x, state y) {
    return (x.v < y.v);
}  

vector<edge> g[N];
vector<int> order;
bool us[N];

pair<ll, int> dp[N][2][2];
map<ll, ll> S[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
        cin >> C[i] >> P[i];
    }
    for(int i = 1; i <= n; i++) {
        for(auto [to, x] : g[i]) {
            S[i][C[x]] += P[x];
        }
    }

    set<pair<ll, state>> St;
    for(int i = 1; i <= n; i++) {
        dp[i][0][0] = dp[i][0][1] = {(i < n ? INF : 0), -1},
        dp[i][1][0] = dp[i][1][1] = {(i < n ? INF : 0), -1};
        for(int j = 0; j <= 1; j++) {
            for(int k = 0; k <= 1; k++) {
                St.insert({dp[i][j][k].first, {i, j, k, -1}});
            }
        }
    }
    bool processed[n + 1] = {};
    while(!St.empty()) {
        state t = (St.begin())->second;
        int cur = t.v, st = t.st, ix = t.ix, color = t.color;
        ll curdp = dp[cur][st][ix].first;

        St.erase(St.begin());
        processed[cur] = 1;

        for(auto [to, i] : g[cur]) {
            if(processed[to]) continue;
            for(int next_st = 0; next_st <= 1; next_st++) {
                St.erase({dp[to][next_st][0].first, {to, next_st, dp[to][next_st][0].second}});
                St.erase({dp[to][next_st][1].first, {to, next_st, dp[to][next_st][1].second}});
                
                ll newdp = INF, cl = C[i];
                if(next_st) newdp = curdp + (S[to][cl] - P[i]);
                else newdp = curdp + P[i] * (cl != color || !st);
                
                if(dp[to][next_st][0].second == cl)     
                    dp[to][next_st][0].first = min(dp[to][next_st][0].first, newdp);
                
                if(dp[to][next_st][1].second == cl)     
                    dp[to][next_st][1].first = min(dp[to][next_st][1].first, newdp);
                
                if(dp[to][next_st][0].first > dp[to][next_st][1].first) 
                    swap(dp[to][next_st][0], dp[to][next_st][1]);
                
                if(newdp < dp[to][next_st][0].first) 
                    swap(dp[to][next_st][0], dp[to][next_st][1]),
                    dp[to][next_st][0] = {newdp, cl};
                else if(newdp < dp[to][next_st][1].first) 
                    dp[to][next_st][1] = {newdp, cl};
                
                St.insert({dp[to][next_st][0].first, {to, next_st, 0, dp[to][next_st][0].second}});
                St.insert({dp[to][next_st][1].first, {to, next_st, 1, dp[to][next_st][0].second}});
            }   
        }
    }

    ll res = min(dp[1][0][0].first, dp[1][1][0].first);
    cout << (res == INF ? -1 : res);
}

    // for(int cur : order) {
    //     if(cur == n) {
    //         continue;
    //     }
    //     dp[cur][0][0] = dp[cur][0][1] = {INF, -1};
    //     dp[cur][1][0] = dp[cur][1][1] = {INF, -1};

    //     vector<pair<int, int>> pr;
    //     for(auto [to, i] : g[cur]) 
    //         if(tin[to] < tin[cur]) pr.push_back({to, i});
    //     map<int, int> S;
        
    //     map<int, ll> ans[2];
    //     for(auto [to, i] : g[cur]) {
    //         S[C[i]] += P[i];
    //     }    
    //     for(auto [next, i] : pr) {
    //         for(int st = 0; st <= 1; st++) {
    //             ans[st][C[i]] = INF;
    //             for(int next_st = 0; next_st <= 1; next_st++) {
    //                 ans[st][C[i]] = min(ans[st][C[i]], dp[next][next_st][0].first + (st ? S[C[i]] - P[i] : P[i]));
    //             }
    //         }
    //         ans[0][C[i]] = min(ans[0][C[i]], dp[next][1][0].first + (dp[next][1][0].second != C[i]) * P[i]);
    //         ans[0][C[i]] = min(ans[0][C[i]], dp[next][1][1].first + (dp[next][1][1].second != C[i]) * P[i]);
    //     }
    //     for(int st = 0; st <= 1; st++) {
    //         dp[cur][st][0] = {(--ans[st].end())->second, (--ans[st].end())->first};
    //         if((int)ans[st].size() > 1) {
    //             dp[cur][st][1] = {(--(--ans[st].end()))->second, (--(--ans[st].end()))->first};
    //         }
    //     }
    // }
    // ll res = INF;
    // for(int st = 0; st <= 1; st++) 
    //     res = min(dp[1][st][0].first, res);
    // cout << (res == INF ? -1 : res);

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7356 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7408 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7476 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Incorrect 6 ms 7780 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 18988 KB Output is correct
2 Correct 79 ms 13576 KB Output is correct
3 Correct 251 ms 17548 KB Output is correct
4 Correct 157 ms 16416 KB Output is correct
5 Incorrect 810 ms 45812 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7356 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7408 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 7476 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Incorrect 6 ms 7780 KB Output isn't correct
10 Halted 0 ms 0 KB -