oj.uz

Submission #1111135

# Submission time Handle Problem Language Result Execution time Memory
1111135 2024-11-11T15:09:58 Z cpptowin Relay Marathon (NOI20_relaymarathon) C++17
25 / 100
 1605 ms 180184 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 100010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    x %= mod;
    if(x < 0) x += mod;
}
void del(int &x, int k)
{
    x -= k;
    x %= mod;
    if(x < 0) x += mod;
}
int n,m,k;
vii ke[maxn];
vi special;
int d[maxn];
int sources[maxn];
pii dist[maxn];
int mindist;
pii node;
void dijkstra(vi inp)
{
    mindist = inf;
    fo(i,1,n) d[i] = inf;
    priority_queue<pii,vii,greater<pii>> q;
    for(int it : inp)
    {
        d[it] = 0;
        sources[it] = it;
        q.push({0,it});
    }
    while(ss(q))
    {
        auto [du,u] = q.top();
        q.pop();
        if(du != d[u]) continue;
        for(auto [v,w] : ke[u])
        {
            if(minimize(d[v],du + w))
            {
                q.push({d[v],v});
                sources[v] = sources[u];
            }
        }
    }
    fo(u,1,n) for(auto [v,w] : ke[u]) if(sources[u] != sources[v])
        {
            if(minimize(mindist,d[u] + w + d[v])) node = {sources[u],sources[v]};
        }
}
pii min1,min2;
void dij(int inp)
{
    min1.fi = inf;
    min2.fi = inf;
    fo(i,1,n) d[i] = inf;
    d[inp] = 0;
    priority_queue<pii,vii,greater<pii>> q;
    q.push({0,inp});
    while(q.size())
    {
        auto [du,u] = q.top();
        q.pop();
        if(d[u] != du) continue;
        for(auto [v,w] : ke[u])
        {
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                q.push({d[v],v});
            }
        }
    }
    for(int it : special) if(it != inf)
        {
            if(min1.fi > d[it])
            {
                min2 = min1;
                min1 = {d[it],it};
            }
        }
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> k;
    special.resize(k);
    fo(i,1,m)
    {
        int u,v,w;
        cin >> u >> v >> w;
        ke[u].pb(v,w);
        ke[v].pb(u,w);
    }
    int res = inf;
    for(int &it : special) cin >> it;
    dijkstra(special);
    int d1 = mindist;
    vi cc;
    for(int it : special) if(it != node.fi and it != node.se) cc.pb(it);
    dijkstra(cc);
    minimize(res,mindist + d1);
    dij(node.fi);
    pii x = min1;
    pii y = min2;
    dij(node.se);
    if(x.se == node.se)
    {
        int cc = inf;
        for(int it : special) if(it != node.fi and it != node.se and it != y.se) minimize(cc,d[it]);
        minimize(res,y.fi + cc);
    }
    else
    {
        int cc = inf;
        for(int it : special) if(it != node.fi and it != node.se and it != x.se) minimize(cc,d[it]);
        minimize(res,x.fi + cc);
    }
    dij(node.se);
    x = min1;
    y = min2;
    dij(node.fi);
    if(x.se == node.fi)
    {
        int cc = inf;
        for(int it : special) if(it != node.fi and it != node.se and it != y.se) minimize(cc,d[it]);
        minimize(res,y.fi + cc);
    }
    else
    {
        int cc = inf;
        for(int it : special) if(it != node.fi and it != node.se and it != x.se) minimize(cc,d[it]);
        minimize(res,x.fi + cc);
    }
    cout << res;
}

Compilation message

RelayMarathon.cpp:128:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  128 | main()
      | ^~~~
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 12.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 10712 KB Output is correct
2 Correct 5 ms 6224 KB Output is correct
3 Correct 1445 ms 172932 KB Output is correct
4 Correct 794 ms 78872 KB Output is correct
5 Correct 201 ms 19056 KB Output is correct
6 Correct 151 ms 15668 KB Output is correct
7 Correct 221 ms 20960 KB Output is correct
8 Correct 72 ms 10960 KB Output is correct
9 Correct 138 ms 14812 KB Output is correct
10 Correct 103 ms 12224 KB Output is correct
11 Correct 1605 ms 178848 KB Output is correct
12 Correct 112 ms 12780 KB Output is correct
13 Correct 521 ms 53796 KB Output is correct
14 Correct 215 ms 21040 KB Output is correct
15 Correct 1480 ms 175728 KB Output is correct
16 Correct 47 ms 10064 KB Output is correct
17 Correct 1047 ms 121752 KB Output is correct
18 Correct 5 ms 6272 KB Output is correct
19 Correct 1450 ms 180184 KB Output is correct
20 Correct 227 ms 19892 KB Output is correct
21 Correct 183 ms 17992 KB Output is correct
22 Correct 89 ms 11940 KB Output is correct
23 Correct 15 ms 8528 KB Output is correct
24 Correct 997 ms 136652 KB Output is correct
25 Correct 145 ms 13624 KB Output is correct
26 Correct 73 ms 11004 KB Output is correct
27 Correct 120 ms 13480 KB Output is correct
28 Correct 10 ms 7504 KB Output is correct
29 Correct 233 ms 20152 KB Output is correct
30 Correct 409 ms 38516 KB Output is correct

Subtask #4
0 / 58.0

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