oj.uz

Submission #676050

# Submission time Handle Problem Language Result Execution time Memory
676050 2022-12-29T08:01:46 Z Cookie Cheap flights (LMIO18_pigus_skrydziai) C++14
16 / 100
 1395 ms 35268 KB 
#include<bits/stdc++.h>
 
#include<fstream>
 
using namespace std;
ifstream fin("talent.in");
ofstream fout("talent.out");
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
//#define int long long
typedef unsigned long long ull;
const int mxn = 3e5 + 3;
int n, m;
ll c[mxn + 1];
struct e{
    ll u, v, w;
};
vt<e>edge;
vt<pii>adj[mxn + 1];
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    forr(i, 0, m){
        int u, v; cin >> u >> v; ll w; cin >> w;
        adj[u].pb({v, w}); adj[v].pb({u, w});
        edge.pb({u, v, w});
        c[u] += w; c[v] += w;
    }
    ll ans  =0;
    forr(i, 1, n + 1)ans = max(ans, c[i]);
    // triangle
    for(auto [u, v, w]: edge){
        bool swapp = adj[u].size() > adj[v].size();
        if(swapp)swap(adj[u], adj[v]);
        for(auto [t, e]: adj[u]){
            int id = lower_bound(adj[v].begin(), adj[v].end(), make_pair(t, -1)) - adj[v].begin();
            if(id != adj[v].size() && adj[v][id].fi == t){
                //cout << u << " " << v  << " " << t << "\n";
                ans = max(ans, e + w + adj[v][id].se);
            }
        }
        if(swapp)swap(adj[u], adj[v]);
    }
    cout << ans;
    return 0;
}

Compilation message

pigus_skrydziai.cpp: In function 'int main()':
pigus_skrydziai.cpp:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for(auto [u, v, w]: edge){
      |              ^
pigus_skrydziai.cpp:43:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         for(auto [t, e]: adj[u]){
      |                  ^
pigus_skrydziai.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             if(id != adj[v].size() && adj[v][id].fi == t){
      |                ~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7336 KB Output is correct
6 Correct 74 ms 8632 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Incorrect 4 ms 7380 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7336 KB Output is correct
6 Correct 74 ms 8632 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Incorrect 4 ms 7380 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 26164 KB Output is correct
2 Correct 248 ms 35268 KB Output is correct
3 Correct 73 ms 15020 KB Output is correct
4 Correct 125 ms 22856 KB Output is correct
5 Correct 226 ms 34024 KB Output is correct
6 Correct 1395 ms 13432 KB Output is correct
7 Correct 91 ms 27224 KB Output is correct
8 Correct 99 ms 34028 KB Output is correct
9 Correct 6 ms 9624 KB Output is correct
10 Correct 1387 ms 13616 KB Output is correct
11 Correct 114 ms 31432 KB Output is correct
12 Correct 942 ms 19628 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 237 ms 13156 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 26164 KB Output is correct
2 Correct 248 ms 35268 KB Output is correct
3 Correct 73 ms 15020 KB Output is correct
4 Correct 125 ms 22856 KB Output is correct
5 Correct 226 ms 34024 KB Output is correct
6 Correct 1395 ms 13432 KB Output is correct
7 Correct 91 ms 27224 KB Output is correct
8 Correct 99 ms 34028 KB Output is correct
9 Correct 6 ms 9624 KB Output is correct
10 Correct 1387 ms 13616 KB Output is correct
11 Correct 114 ms 31432 KB Output is correct
12 Correct 942 ms 19628 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 237 ms 13156 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 5 ms 7380 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 4 ms 7336 KB Output is correct
20 Correct 74 ms 8632 KB Output is correct
21 Correct 4 ms 7380 KB Output is correct
22 Correct 4 ms 7380 KB Output is correct
23 Correct 4 ms 7380 KB Output is correct
24 Incorrect 4 ms 7380 KB Output isn't correct
25 Halted 0 ms 0 KB -