oj.uz

Submission #198472

# Submission time Handle Problem Language Result Execution time Memory
198472 2020-01-26T07:32:52 Z oolimry Cheap flights (LMIO18_pigus_skrydziai) C++14
16 / 100
 1427 ms 102800 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<long long,long long> ii; 
static vector<ii> adj[500005];
static vector<ii> tree[500005];
map<ii, long long> thonk;
class UFDS {
typedef vector<int> vi;
public:
    vi p, rak, setSize;
    int numSets;

    void create(int n){
        setSize.assign(n, 1);
        numSets = n;
        rak.assign(n, 0);
        p.assign(n, 0);
        for(int i =0;i < n;i++){
            p[i] = i;
        }
    }

    int findSet(int i){
        return (p[i] == i) ? i : (p[i] = findSet(p[i]));
    }

    bool isSameSet(int i, int j){
        return findSet(i) == findSet(j);
    }

    bool unionSet(int i, int j){
        if(isSameSet(i,j))
            return false;
        numSets--;
        int x = findSet(i);
        int y = findSet(j);

        if(rak[x] > rak[y]) {
            p[y] = x; setSize[x] += setSize[y];
        }

        else {
            p[x] = y; setSize[y] += setSize[x];
            if(rak[x] == rak[y]) rak[y]++;
        }
		return true;
    }
} uf;

struct edge{
	long long u;
	long long v;
	long long w;
};

bool comp(edge a, edge b){
	return a.w > b.w;
}
int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n, m; cin >> n >> m;
	edge edges[m];
	
	uf.create(n);

	for(long long i = 0;i < m;i++){
		long long u, v; long long w;
		cin >> u >> v >> w; u--; v--;
		adj[u].push_back(ii(v,w));
		adj[v].push_back(ii(u,w));
		edges[i] = {u,v,w};
		thonk[ii(u,v)] = w;
		thonk[ii(v,u)] = w;
	}
	
	long long ans = 0;
	
	for(long long i = 0;i < n;i++){
		long long acc = 0;
		for(ii v : adj[i]) acc += v.second;
		ans = max(ans, acc);
	}
	
	sort(edges,edges+m,comp);
	
	for(edge e : edges){
		if(uf.unionSet(e.u, e.v)){
			tree[e.u].push_back(ii(e.v,e.w));
			tree[e.v].push_back(ii(e.u,e.w));
		}
	}
	
	if(n <= 200){
		for(int a = 0;a < n;a++){
			for(int b = 0;b < n;b++){
				for(int c = 0;c < n;c++){
					ans = max(ans, thonk[ii(a,b)] + thonk[ii(c,b)] + thonk[ii(a,c)]);
				}
			}
		}
	}
	
	for(long long i = 0;i < n;i++){
		if(tree[i].size() == 2){
			ii u = tree[i][0];
			ii v = tree[i][1];
			if(thonk.find(ii(u.first,v.first)) != thonk.end()){
				ans = max(ans, u.second + v.second + thonk[ii(u.first,v.first)]);
			}
		}
	}
	
	cout << ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 21 ms 23800 KB Output is correct
3 Incorrect 20 ms 23800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 21 ms 23800 KB Output is correct
3 Incorrect 20 ms 23800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 68416 KB Output is correct
2 Correct 1215 ms 99704 KB Output is correct
3 Correct 300 ms 49272 KB Output is correct
4 Correct 790 ms 75128 KB Output is correct
5 Correct 1427 ms 94952 KB Output is correct
6 Correct 157 ms 46456 KB Output is correct
7 Correct 337 ms 88312 KB Output is correct
8 Correct 390 ms 97016 KB Output is correct
9 Correct 27 ms 27640 KB Output is correct
10 Correct 153 ms 46468 KB Output is correct
11 Correct 403 ms 92768 KB Output is correct
12 Correct 333 ms 69240 KB Output is correct
13 Correct 1397 ms 26488 KB Output is correct
14 Correct 279 ms 43128 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 68416 KB Output is correct
2 Correct 1215 ms 99704 KB Output is correct
3 Correct 300 ms 49272 KB Output is correct
4 Correct 790 ms 75128 KB Output is correct
5 Correct 1427 ms 94952 KB Output is correct
6 Correct 157 ms 46456 KB Output is correct
7 Correct 337 ms 88312 KB Output is correct
8 Correct 390 ms 97016 KB Output is correct
9 Correct 27 ms 27640 KB Output is correct
10 Correct 153 ms 46468 KB Output is correct
11 Correct 403 ms 92768 KB Output is correct
12 Correct 333 ms 69240 KB Output is correct
13 Correct 1397 ms 26488 KB Output is correct
14 Correct 279 ms 43128 KB Output is correct
15 Correct 797 ms 66884 KB Output is correct
16 Correct 755 ms 61900 KB Output is correct
17 Correct 814 ms 71912 KB Output is correct
18 Correct 1141 ms 78848 KB Output is correct
19 Correct 281 ms 49640 KB Output is correct
20 Correct 1097 ms 83148 KB Output is correct
21 Correct 1191 ms 102800 KB Output is correct
22 Correct 759 ms 76480 KB Output is correct
23 Correct 840 ms 87624 KB Output is correct
24 Correct 506 ms 56532 KB Output is correct
25 Correct 1163 ms 84224 KB Output is correct
26 Correct 1120 ms 81964 KB Output is correct
27 Correct 1172 ms 78968 KB Output is correct
28 Correct 21 ms 23800 KB Output is correct
29 Correct 21 ms 23800 KB Output is correct
30 Incorrect 20 ms 23800 KB Output isn't correct
31 Halted 0 ms 0 KB -