oj.uz

Submission #258788

# Submission time Handle Problem Language Result Execution time Memory
258788 2020-08-06T14:44:39 Z uacoder123 Cheap flights (LMIO18_pigus_skrydziai) C++14
16 / 100
 1394 ms 67500 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef vector <lli> vi;
map<ii,lli> ma;
vector<ii> al[300001];
int main()
{
    lli n,m;
    cin>>n>>m;
    for(lli i=0;i<m;++i)
    {
        lli f,s,w;
        cin>>f>>s>>w;
        al[f].pb(mp(w,s));
        al[s].pb(mp(w,f));
        ma[mp(f,s)]=w;
        ma[mp(s,f)]=w;
    }
    lli ans=0;
    for(lli i=1;i<=n;++i)
    {
        sort(all(al[i]));
        lli s=0;
        for(lli j=0;j<al[i].size();++j)
            s+=al[i][j].F;
        if(al[i].size()>1&&ma.find(mp(al[i][0].S,al[i][1].S))!=ma.end())
            s=max(s,al[i][0].F+al[i][1].F+ma[mp(al[i][0].S,al[i][1].S)]);
        ans=max(ans,s);
    }
    cout<<ans<<endl;
    return(0);
}

Compilation message

pigus_skrydziai.cpp: In function 'int main()':
pigus_skrydziai.cpp:37:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(lli j=0;j<al[i].size();++j)
                     ~^~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7296 KB Output is correct
2 Correct 5 ms 7296 KB Output is correct
3 Correct 5 ms 7296 KB Output is correct
4 Correct 4 ms 7296 KB Output is correct
5 Correct 5 ms 7296 KB Output is correct
6 Correct 36 ms 10872 KB Output is correct
7 Correct 5 ms 7424 KB Output is correct
8 Correct 4 ms 7424 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Incorrect 5 ms 7424 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7296 KB Output is correct
2 Correct 5 ms 7296 KB Output is correct
3 Correct 5 ms 7296 KB Output is correct
4 Correct 4 ms 7296 KB Output is correct
5 Correct 5 ms 7296 KB Output is correct
6 Correct 36 ms 10872 KB Output is correct
7 Correct 5 ms 7424 KB Output is correct
8 Correct 4 ms 7424 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Incorrect 5 ms 7424 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 415 ms 36088 KB Output is correct
2 Correct 1022 ms 60792 KB Output is correct
3 Correct 323 ms 25532 KB Output is correct
4 Correct 618 ms 44792 KB Output is correct
5 Correct 1394 ms 64888 KB Output is correct
6 Correct 196 ms 28264 KB Output is correct
7 Correct 472 ms 55376 KB Output is correct
8 Correct 576 ms 63488 KB Output is correct
9 Correct 7 ms 7552 KB Output is correct
10 Correct 195 ms 28280 KB Output is correct
11 Correct 531 ms 64476 KB Output is correct
12 Correct 422 ms 49220 KB Output is correct
13 Correct 5 ms 7424 KB Output is correct
14 Correct 267 ms 25208 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 36088 KB Output is correct
2 Correct 1022 ms 60792 KB Output is correct
3 Correct 323 ms 25532 KB Output is correct
4 Correct 618 ms 44792 KB Output is correct
5 Correct 1394 ms 64888 KB Output is correct
6 Correct 196 ms 28264 KB Output is correct
7 Correct 472 ms 55376 KB Output is correct
8 Correct 576 ms 63488 KB Output is correct
9 Correct 7 ms 7552 KB Output is correct
10 Correct 195 ms 28280 KB Output is correct
11 Correct 531 ms 64476 KB Output is correct
12 Correct 422 ms 49220 KB Output is correct
13 Correct 5 ms 7424 KB Output is correct
14 Correct 267 ms 25208 KB Output is correct
15 Correct 667 ms 45908 KB Output is correct
16 Correct 734 ms 43940 KB Output is correct
17 Correct 787 ms 48456 KB Output is correct
18 Correct 1043 ms 58736 KB Output is correct
19 Correct 309 ms 26360 KB Output is correct
20 Correct 1090 ms 64544 KB Output is correct
21 Correct 1105 ms 67500 KB Output is correct
22 Correct 673 ms 47096 KB Output is correct
23 Correct 791 ms 54620 KB Output is correct
24 Correct 438 ms 35668 KB Output is correct
25 Correct 1113 ms 63224 KB Output is correct
26 Correct 1020 ms 60720 KB Output is correct
27 Correct 1028 ms 58700 KB Output is correct
28 Correct 5 ms 7296 KB Output is correct
29 Correct 5 ms 7296 KB Output is correct
30 Correct 5 ms 7296 KB Output is correct
31 Correct 4 ms 7296 KB Output is correct
32 Correct 5 ms 7296 KB Output is correct
33 Correct 36 ms 10872 KB Output is correct
34 Correct 5 ms 7424 KB Output is correct
35 Correct 4 ms 7424 KB Output is correct
36 Correct 5 ms 7424 KB Output is correct
37 Incorrect 5 ms 7424 KB Output isn't correct
38 Halted 0 ms 0 KB -