oj.uz

Submission #791610

# Submission time Handle Problem Language Result Execution time Memory
791610 2023-07-24T08:00:22 Z Cookie Cheap flights (LMIO18_pigus_skrydziai) C++14
16 / 100
 1135 ms 40240 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]){
          if(t == v)continue;
            int id = lower_bound(adj[v].begin(), adj[v].end(), make_pair(t, (ll)-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:46:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             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 3 ms 7364 KB Output is correct
3 Correct 3 ms 7384 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 63 ms 9104 KB Output is correct
7 Correct 6 ms 7380 KB Output is correct
8 Correct 5 ms 7380 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Incorrect 3 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 3 ms 7364 KB Output is correct
3 Correct 3 ms 7384 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 63 ms 9104 KB Output is correct
7 Correct 6 ms 7380 KB Output is correct
8 Correct 5 ms 7380 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Incorrect 3 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 74 ms 26244 KB Output is correct
2 Correct 183 ms 40240 KB Output is correct
3 Correct 49 ms 17012 KB Output is correct
4 Correct 119 ms 26632 KB Output is correct
5 Correct 212 ms 38932 KB Output is correct
6 Correct 988 ms 15632 KB Output is correct
7 Correct 73 ms 31260 KB Output is correct
8 Correct 99 ms 38112 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 982 ms 15656 KB Output is correct
11 Correct 94 ms 35160 KB Output is correct
12 Correct 1135 ms 23812 KB Output is correct
13 Correct 4 ms 7388 KB Output is correct
14 Correct 252 ms 15300 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 26244 KB Output is correct
2 Correct 183 ms 40240 KB Output is correct
3 Correct 49 ms 17012 KB Output is correct
4 Correct 119 ms 26632 KB Output is correct
5 Correct 212 ms 38932 KB Output is correct
6 Correct 988 ms 15632 KB Output is correct
7 Correct 73 ms 31260 KB Output is correct
8 Correct 99 ms 38112 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 982 ms 15656 KB Output is correct
11 Correct 94 ms 35160 KB Output is correct
12 Correct 1135 ms 23812 KB Output is correct
13 Correct 4 ms 7388 KB Output is correct
14 Correct 252 ms 15300 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 3 ms 7364 KB Output is correct
17 Correct 3 ms 7384 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 3 ms 7380 KB Output is correct
20 Correct 63 ms 9104 KB Output is correct
21 Correct 6 ms 7380 KB Output is correct
22 Correct 5 ms 7380 KB Output is correct
23 Correct 3 ms 7380 KB Output is correct
24 Incorrect 3 ms 7380 KB Output isn't correct
25 Halted 0 ms 0 KB -