oj.uz

답안 #795926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
795926 2023-07-27T22:48:06 Z allllekssssa Cheap flights (LMIO18_pigus_skrydziai) C++14
0 / 100
 256 ms 66400 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

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 47152 KB Output is correct
2 Correct 24 ms 47244 KB Output is correct
3 Correct 24 ms 47188 KB Output is correct
4 Correct 25 ms 47164 KB Output is correct
5 Correct 24 ms 47188 KB Output is correct
6 Correct 33 ms 47860 KB Output is correct
7 Correct 24 ms 47196 KB Output is correct
8 Incorrect 23 ms 47240 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 47152 KB Output is correct
2 Correct 24 ms 47244 KB Output is correct
3 Correct 24 ms 47188 KB Output is correct
4 Correct 25 ms 47164 KB Output is correct
5 Correct 24 ms 47188 KB Output is correct
6 Correct 33 ms 47860 KB Output is correct
7 Correct 24 ms 47196 KB Output is correct
8 Incorrect 23 ms 47240 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 63660 KB Output is correct
2 Correct 177 ms 66400 KB Output is correct
3 Correct 63 ms 53596 KB Output is correct
4 Correct 110 ms 61268 KB Output is correct
5 Incorrect 256 ms 63616 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 63660 KB Output is correct
2 Correct 177 ms 66400 KB Output is correct
3 Correct 63 ms 53596 KB Output is correct
4 Correct 110 ms 61268 KB Output is correct
5 Incorrect 256 ms 63616 KB Output isn't correct
6 Halted 0 ms 0 KB -