oj.uz

Submission #795925

# Submission time Handle Problem Language Result Execution time Memory
795925 2023-07-27T22:44:14 Z vjudge1 Cheap flights (LMIO18_pigus_skrydziai) C++17
0 / 100
 204 ms 66524 KB 
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int, int>

const int maxN = 1e6 + 10;

vector<pii> v[maxN], v1[maxN];
long long cnt[maxN];
int n, m;
int mx;

int main() {

    cin >> n >> m;
	

    for (int i = 1; i<=m; i++) {
    	int x, y, z;
    	scanf("%d%d%d", &x, &y, &z);
    	cnt[x]+=z;
    	cnt[y]+=z;
    	v[x].pb(mp(y,z));
    	v[y].pb(mp(x, z));
    }


    long long ans = 0;

    for (int i = 1; i<=n; i++) {
    	ans = max(ans, cnt[i]);
    }


    for (int i = 1; i<= n; i++) {
    	for (auto j: v[i]) {
    		if (j.first > i) continue;
    		int x = i;
    		int y = j.first;
    		int z = j.second;
    		if (v[x].size() > v[y].size()) swap(x, y);
    		v1[x].pb(mp(y, z));
    	}
    }

    for (int i = 1; i<=n; i++) {
    	for (auto j: v1[i]) {

    		for (auto k: v1[i])
    			cnt[k.first] = k.second;

    		for (auto k: v1[j.first]) {
    			cnt[k.first]+=k.second;
    			ans = max(ans, j.second + cnt[k.first]);
    			cnt[k.first] = 0;
    		}

    		for (auto k: v1[i]) {
    			cnt[k.first] = 0;
    		}

    	}
    }

    cout << ans << endl;

	return 0;
}

Compilation message

pigus_skrydziai.cpp: In function 'int main()':
pigus_skrydziai.cpp:27:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |      scanf("%d%d%d", &x, &y, &z);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 25 ms 47208 KB Output is correct
3 Correct 24 ms 47244 KB Output is correct
4 Correct 23 ms 47196 KB Output is correct
5 Correct 23 ms 47188 KB Output is correct
6 Correct 32 ms 47860 KB Output is correct
7 Correct 23 ms 47188 KB Output is correct
8 Incorrect 23 ms 47188 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Correct 25 ms 47208 KB Output is correct
3 Correct 24 ms 47244 KB Output is correct
4 Correct 23 ms 47196 KB Output is correct
5 Correct 23 ms 47188 KB Output is correct
6 Correct 32 ms 47860 KB Output is correct
7 Correct 23 ms 47188 KB Output is correct
8 Incorrect 23 ms 47188 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 63688 KB Output is correct
2 Correct 175 ms 66524 KB Output is correct
3 Correct 62 ms 53612 KB Output is correct
4 Correct 109 ms 61228 KB Output is correct
5 Incorrect 204 ms 63604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 63688 KB Output is correct
2 Correct 175 ms 66524 KB Output is correct
3 Correct 62 ms 53612 KB Output is correct
4 Correct 109 ms 61228 KB Output is correct
5 Incorrect 204 ms 63604 KB Output isn't correct
6 Halted 0 ms 0 KB -