oj.uz

Submission #877018

# Submission time Handle Problem Language Result Execution time Memory
877018 2023-11-22T17:48:21 Z efedmrlr Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 101 ms 6316 KB 
#include <bits/stdc++.h>
using namespace std;

#define n_l '\n'
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; cout << to_string(__VA_ARGS__) << endl
template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); } 
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgm(__VA_ARGS__); cout << endl


#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e16;
const int N = 205;
const int M = 1005;
const int ALPH = 26;
const int LGN = 25;
const int MOD = 1e9+7;
int n,m,q;
vector<array<int,4> > edges;
vector<int> spA, spA_r, spB, spB_r;
int ans = INF;

int mult(int x, int y) {
    return x*y%MOD;
} 
int add(int x, int y) {
    return (x+y)%MOD;
}



void dijkstra(vector<vector<array<int,2> > > &adj, vector<int> &sp, int src, vector<vector<int> > &nds) {
    priority_queue<array<int,3> , vector<array<int,3> >, greater<array<int,3> > > pq;
    nds.assign(n+5, vector<int>());
    sp.assign(n+5, INF);
    pq.push({0, src, 0});
    while(pq.size()) {
        auto cur = pq.top();
        pq.pop();
        if(sp[cur[1]] != INF) {
            if(cur[0] == sp[cur[1]]) {
                nds[cur[1]].pb(cur[2]);
            }   
            continue;
        }
        sp[cur[1]] = cur[0];
        nds[cur[1]].pb(cur[2]);
        for(auto c : adj[cur[1]]) {

            pq.push({cur[0] + c[1], c[0], cur[1]});
        }
    }
}
void dfs(int node, vector<int> &vis, vector<int> &topo, vector<vector<int> > &lst, int fin, vector<vector<int> > &nadj) {
    vis[node] = 1;
    if(node == fin) vis[node] = 2;
    for(auto c : lst[node]) {
        if(vis[c] == 2) {
            vis[node] = 2;
            nadj[node].pb(c);
        } 
        if(vis[c]) continue;
        dfs(c, vis, topo, lst, fin, nadj);
        if(vis[c] == 2) {
            vis[node] = 2;
            nadj[node].pb(c);
        }
    }
    if(vis[node] == 2)
    {
        topo.pb(node);
    }
}
void find_dp(vector<int> &dp, vector<vector<int> > &nds, int src, int fin) {
    vector<int> topo;
    vector<int> vis(n+3, 0);
    vector<vector<int> > nadj(n+3, vector<int>());
    
    dfs(src, vis, topo, nds, fin, nadj);
    
    swap(nds, nadj);
    reverse(topo.begin(), topo.end());
    dp.assign(n+3, 0);
    dp[src] = 1ll;
    for(auto i : topo) {
        for(auto c : nds[i]) {
            dp[c] = add(dp[c], dp[i]);
        }
    }
    
}
void find_dps(vector<int> &dp, vector<int> &dpr, vector<vector<int> > &nds, vector<vector<int> > &nds_r, int src, int fin) {
    find_dp(dp, nds, src, fin);
    find_dp(dpr, nds_r, fin, src);
    
}

bool calcX(array<int,4> &edge, vector<int> &dp, vector<int> &dpr, int src, int fin, vector<vector<int> > &dag) {
    bool is_crit = 0;
    if(mult(dp[edge[0]] , dpr[edge[1]]) == dp[fin] && dag[edge[0]].size() == 1 && dag[edge[0]][0] == edge[1]) {
        is_crit = 1;
    }
    return is_crit;
}
int dijkstra_again(int src, int fin, array<int,4> &eg) {
    vector<vector<array<int,2> > > adj(n+3, vector<array<int,2> >());
    vector<int> sp;
    vector<vector<int> > trash;
    adj[eg[1]].pb({eg[0], eg[2]});
    for(auto &c : edges) {
        if(&c == &eg) continue;
        adj[c[0]].pb({c[1], c[2]});
    }
    
    dijkstra(adj, sp, src, trash);
    return sp[fin];
}
inline void solve() {
    cin>>n>>m;
    edges.resize(m+3);
    REP(i,m) {
        cin>>edges[i][0]>>edges[i][1]>>edges[i][2]>>edges[i][3];

    }
    
    vector<vector<array<int,2> > > adj(n + 3, vector<array<int,2> >());
    vector<vector<int> > dagA, dagA_r, dagB, dagB_r;
    vector<int> dp, dpr;
    for(auto c : edges) {
        adj[c[0]].pb({c[1], c[2]});
    }
    dijkstra(adj, spA, 1, dagA);
    dijkstra(adj, spB, n, dagB);
    
    adj.assign(n+3, vector<array<int,2> >(0));
    for(auto c : edges) {
        adj[c[1]].pb({c[0], c[2]});
    }
    dijkstra(adj, spA_r, 1, dagA_r);
    dijkstra(adj, spB_r, n, dagB_r);

    ans = min(ans, spA[n] + spB[1]);
    // cout<<"init:\n";
    // dbg(ans);

    find_dps(dp, dpr, dagB_r, dagA, 1, n);
    /*
    for(auto eg : edges) {
        dbg(spA[eg[1]]); dbg(spB_r[eg[0]]); dbg(spB[eg[1]]); dbg(spB_r[eg[0]]);
        int ret = (spA[eg[1]] + spB_r[eg[0]] + eg[2]) + (spB[eg[1]] + spA_r[eg[0]] + eg[2]);
        dbg(eg);
        ret += eg[3];
        dbg(ret);
        ans = min(ans , ret); 
    }
    */
    // dbg(ans);
    // cout<<"first part:\n";
    for(auto &eg : edges) {
        bool crit = calcX(eg, dp, dpr, 1, n, dagB_r);
        // dbg(eg);
        // cout<<"crit:"<<crit<<endl;
        int costBA = spB[eg[1]] + spA_r[eg[0]] + eg[2] + eg[3];
        // cout<<"costBA:"<<costBA<<endl;
        int ret = costBA;
        if(crit) {
            ret += dijkstra_again(1, n, eg);
            ans = min(ans, ret);
        }  
        else {
            ret += spA[n];
            ans = min(ans , ret);
        }
        // dbg(ret);
    }
    find_dps(dp, dpr, dagA_r, dagB, n, 1);
    for(auto &eg : edges) {
        bool crit = calcX(eg, dp, dpr, n, 1, dagA_r);
        // dbg(eg);
        // cout<<"crit:"<<crit<<endl;
        int costAB = spA[eg[1]] + spB_r[eg[0]] + eg[2] + eg[3];
        // cout<<"costAB:"<<costAB<<endl;
        int ret = costAB;
        if(crit) {
            ret += dijkstra_again(n, 1, eg);
            ans = min(ans ,ret);
        }  
        else {
            ret += spB[1];
            ans = min(ans , ret);
        }
        // dbg(ret);
    }
    if(ans == INF) ans = -1;
    cout<<ans<<"\n";
}
 
signed main() {
    //fastio();
    solve();   
}

Compilation message

ho_t4.cpp: In function 'std::string to_string(std::string, int, int)':
ho_t4.cpp:6:208: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); }
      |                                                                                                                                                                                                             ~~~^~~~~~~~~~
ho_t4.cpp: In function 'void solve()':
ho_t4.cpp:13:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)
      |                          ^
ho_t4.cpp:131:5: note: in expansion of macro 'REP'
  131 |     REP(i,m) {
      |     ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 608 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 500 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 101 ms 544 KB Output is correct
10 Correct 63 ms 852 KB Output is correct
11 Correct 67 ms 604 KB Output is correct
12 Correct 60 ms 600 KB Output is correct
13 Incorrect 1 ms 344 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 6204 KB Output is correct
2 Correct 67 ms 6316 KB Output is correct
3 Correct 74 ms 6088 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 49 ms 4348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 52 ms 4500 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 67 ms 6056 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 45 ms 4412 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 608 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 500 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 101 ms 544 KB Output is correct
10 Correct 63 ms 852 KB Output is correct
11 Correct 67 ms 604 KB Output is correct
12 Correct 60 ms 600 KB Output is correct
13 Incorrect 1 ms 344 KB Output isn't correct
14 Halted 0 ms 0 KB -