oj.uz

Submission #839678

# Submission time Handle Problem Language Result Execution time Memory
839678 2023-08-30T12:19:51 Z thegamercoder19 Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 187 ms 26684 KB 
/*
Coded by thegamercoder19
GL
*/
#define _CRT_SECURE_NO_WARNINGS

#include <bits/stdc++.h>

#define M_PI       3.14159265358979323846
#define FILER 0
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const ll MOD = pow(10, 9) + 7;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const ull INFUL = 0x3f3f3f3f3f3f3f3f;
const ll INFT = 0x3f3f3f3f;
const ll MAX = 1e5+1;
const ll MAXX = 31;
const ll MODD = 998244353;
const double EPS = 1e-10;
const ll B = 350;
#define V vector
#define pll pair<ll, ll>
#define pull2 pair<ull,ull>
#define MS multiset
#define Q queue
#define PQ priority_queue
#define IOF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FOR(typ,i,a,b,c) for(typ i = a; i < b; i += c)
#define FORR(typ,i,a,b,c) for(typ i = a; i > b; i -= c)
#define FORA(a,i) for(auto &i : a)
#define all(v) begin(v), end(v)
#define sz(v) v.size()
#define sorta(a) sort(all(a))
#define sortd(a) sort(all(a), greater<ll>())
#define setp(x) setprecision(x)<<fixed
#define RET return
#define log(a,b) log(b)/log(a)
#define WH(s) while(s)
#define WHI(t) WH(t--)
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define YESNO(s) cout << (s ? "YES" : "NO") << endl;
#define YesNo(s) cout<<(s?"Yes":"No")<<endl;
#define TYP 0
//#define endl '\n'
using namespace std;
struct edge
{
    ll u, v, k;
};
ll n, m, s, t, u, v,x,y,k;
V<V<pll>> g;
V<edge> ge;
ll dijkstra(ll b, ll e)
{
    ll e1 = e;
    V<ll> d(n + 1, INFL), p(n + 1, -1), dp(n + 1, INFL);
    PQ<pll, V<pll>, greater<pll>> pq;
    pq.push({ 0,b });
    d[b] = 0;
    WH(!pq.empty())
    {
        ll u = pq.top().second, du = pq.top().first;
        pq.pop();
        if (du != d[u])continue;
        FORA(g[u], v)
        {
            if (d[v.first] > du + v.second)
            {
                d[v.first] = du + v.second;
                pq.push({ d[v.first], v.first });
                p[v.first] = u;
                //dp[v.first]=dp[u];
            }
            if (d[v.first] == du + v.second)
            {
                dp[v.first] += dp[u];
            }
        }
           
    }
    WH(p[e] != -1)
    {
        g[e].push_back({ p[e],0 }); g[p[e]].push_back({ e,0 });
        e = p[e];
    }
    RET d[e1];
}
void solve()
{
    cin >> n >> m >> s >> t >> u >> v;
    g.resize(n + 1);
    FOR(ll, i, 0, m, 1)
        cin >> x >> y >> k, g[x].push_back({ y,k }), g[y].push_back({ x,k });
    auto ans1 = dijkstra(s, t);
    cout << dijkstra(u, v) << endl;
}
void init()
{

    if (FILER)
    {
        freopen("grassplant.in", "r", stdin);
        freopen("grassplant.out", "w", stdout);
    }

}
void handle()
{
    init();
    ll t = 1;
    if (TYP)cin >> t;
    //getline(cin, s);
    WHI(t)solve();
}

int main()
{
    IOF
        handle();
    RET 0;
}

Compilation message

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:99:10: warning: unused variable 'ans1' [-Wunused-variable]
   99 |     auto ans1 = dijkstra(s, t);
      |          ^~~~
commuter_pass.cpp: In function 'void init()':
commuter_pass.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen("grassplant.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen("grassplant.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 22388 KB Output is correct
2 Correct 162 ms 20992 KB Output is correct
3 Correct 167 ms 26140 KB Output is correct
4 Incorrect 141 ms 21096 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 23900 KB Output is correct
2 Correct 178 ms 23868 KB Output is correct
3 Correct 161 ms 23560 KB Output is correct
4 Correct 173 ms 23724 KB Output is correct
5 Correct 177 ms 24356 KB Output is correct
6 Correct 187 ms 25924 KB Output is correct
7 Correct 173 ms 26684 KB Output is correct
8 Correct 166 ms 24744 KB Output is correct
9 Correct 170 ms 24124 KB Output is correct
10 Correct 157 ms 23528 KB Output is correct
11 Correct 87 ms 16884 KB Output is correct
12 Correct 161 ms 26060 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 22388 KB Output is correct
2 Correct 162 ms 20992 KB Output is correct
3 Correct 167 ms 26140 KB Output is correct
4 Incorrect 141 ms 21096 KB Output isn't correct
5 Halted 0 ms 0 KB -