Submission #1260708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260708		chautanphat	Construction Project 2 (JOI24_ho_t2)	C++20	16 / 100	2094 ms	11312 KiB

Main

/**
｡∠(*・ω･)っ  ⌒ 由 ~    ((　,,・з・,,　))
 _Π_____。
/______/~＼
｜ 田田｜門｜
> love miku so muchhhh <3
**/
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define el "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
// var dec
const int maxn = 2e5 + 3;
const ll INF = 1e18;
int n, m, s, t, l;
ll k;
// ds dec
vector <pii> g[maxn];
//
namespace sub1
{
    bool condition()
    {
        bool ok = 1;
        for (int i=1; i<=n; ++i)
        {
            for (auto &x: g[i])
            {
                ok &= (x.se == 1);
            }
        }
        return (ok && l == 1 && k == 2);
    }
    //
    void solve()
    {
        int ans = 0;
        for (auto &x: g[s])
        {
            int v = x.fi, w = x.se;
            if (v == t) return void(cout << n*(n-1)/2 << el);
            for (auto &y: g[v])
            {
                if (y.fi == t) return void(cout << n*(n-1)/2 << el);
            }
            ans++;
        }
        for (auto &x: g[t])
        {
            ans++;
        }
        cout << ans+1 << el;
    }
}
//
struct State
{
    ll e;
    int u;
    State(ll _e, int _u): e(_e), u(_u) {};
    friend bool operator < (const State& x, const State& y)
    {
        return x.e > y.e;
    }
};
//
void dijkstra(int source, vector<ll>& d)
{
    priority_queue <State, vector<State>> pq;
    pq.push(State(0, source));
    d[source] = 0;
    while (sz(pq))
    {
        ll e = pq.top().e, u = pq.top().u;
        pq.pop();
        if (e != d[u]) continue;
        for (auto &x: g[u])
        {
            int v = x.fi, w = x.se;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                pq.push(State(d[v], v));
            }
        }
    }
}
//
namespace sub3
{
    bool condition()
    {
        return (max(n, m) <= 3000);
    }
    //
    void solve()
    {
        int ans = 0;
        for (int i=1; i<=n; ++i)
        {
            for (int j=i+1; j<=n; ++j)
            {
                g[i].pb({j, l});
                g[j].pb({i, l});
                vector <ll> d(n+3, INF);
                dijkstra(s, d);
                if (d[t] <= k) ++ans;
                g[i].pop_back();
                g[j].pop_back();
            }
        }
        cout << ans << el;
    }
}
//
namespace sub4
{
    void solve()
    {
        vector <ll> distS(n+3, INF), distT(n+3, INF);
        dijkstra(s, distS);
        dijkstra(t, distT);
        vector <ll> dis;
        for (int i=1; i<=n; ++i) dis.pb(distS[i]);
        sort(dis.begin(), dis.end());
        int idx = upper_bound(dis.begin(), dis.end(), 2) - dis.begin();
        ll ans = 0;
        for (int i=1; i<=n; ++i)
        {
            int rem = k-distT[i]-l;
            int cnt = upper_bound(dis.begin(), dis.end(), rem) - dis.begin();
            ans += cnt;
        }
        cout << ans << el;
    }
}
//
void solve()
{
    cin >> n >> m;
    cin >> t >> s >> l >> k;
    for (int i=1; i<=m; ++i)
    {
        int u, v, w; cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    if (sub1::condition()) sub1::solve();
    else if (sub3::condition()) sub3::solve();
    else sub4::solve();
}
//
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("metro.inp", "r"))
    {
        freopen("metro.inp", "r", stdin);
        freopen("metro.out", "w", stdout);
    }
    int t = 1;
//    cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen("metro.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:168:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |         freopen("metro.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 16 / 16
• Subtask 3: 0 / 29
• Subtask 4: 0 / 47