oj.uz

Submission #198471

# Submission time Handle Problem Language Result Execution time Memory
198471 2020-01-26T07:31:55 Z oolimry Cheap flights (LMIO18_pigus_skrydziai) C++14
16 / 100
 1429 ms 102904 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));
		}
	}
	
	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 20 ms 23800 KB Output is correct
3 Correct 21 ms 23800 KB Output is correct
4 Correct 20 ms 23800 KB Output is correct
5 Correct 21 ms 23800 KB Output is correct
6 Correct 40 ms 27640 KB Output is correct
7 Correct 20 ms 23800 KB Output is correct
8 Correct 19 ms 23800 KB Output is correct
9 Correct 20 ms 23800 KB Output is correct
10 Incorrect 21 ms 23800 KB Output isn't correct
11 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 20 ms 23800 KB Output is correct
3 Correct 21 ms 23800 KB Output is correct
4 Correct 20 ms 23800 KB Output is correct
5 Correct 21 ms 23800 KB Output is correct
6 Correct 40 ms 27640 KB Output is correct
7 Correct 20 ms 23800 KB Output is correct
8 Correct 19 ms 23800 KB Output is correct
9 Correct 20 ms 23800 KB Output is correct
10 Incorrect 21 ms 23800 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 462 ms 68456 KB Output is correct
2 Correct 1168 ms 99704 KB Output is correct
3 Correct 293 ms 49144 KB Output is correct
4 Correct 683 ms 75128 KB Output is correct
5 Correct 1429 ms 94956 KB Output is correct
6 Correct 158 ms 46448 KB Output is correct
7 Correct 347 ms 88312 KB Output is correct
8 Correct 391 ms 97016 KB Output is correct
9 Correct 26 ms 27640 KB Output is correct
10 Correct 153 ms 46560 KB Output is correct
11 Correct 392 ms 92900 KB Output is correct
12 Correct 319 ms 69368 KB Output is correct
13 Correct 21 ms 23932 KB Output is correct
14 Correct 265 ms 43000 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 68456 KB Output is correct
2 Correct 1168 ms 99704 KB Output is correct
3 Correct 293 ms 49144 KB Output is correct
4 Correct 683 ms 75128 KB Output is correct
5 Correct 1429 ms 94956 KB Output is correct
6 Correct 158 ms 46448 KB Output is correct
7 Correct 347 ms 88312 KB Output is correct
8 Correct 391 ms 97016 KB Output is correct
9 Correct 26 ms 27640 KB Output is correct
10 Correct 153 ms 46560 KB Output is correct
11 Correct 392 ms 92900 KB Output is correct
12 Correct 319 ms 69368 KB Output is correct
13 Correct 21 ms 23932 KB Output is correct
14 Correct 265 ms 43000 KB Output is correct
15 Correct 794 ms 66796 KB Output is correct
16 Correct 756 ms 62088 KB Output is correct
17 Correct 917 ms 71988 KB Output is correct
18 Correct 1142 ms 78924 KB Output is correct
19 Correct 281 ms 49640 KB Output is correct
20 Correct 1126 ms 83392 KB Output is correct
21 Correct 1176 ms 102904 KB Output is correct
22 Correct 769 ms 76568 KB Output is correct
23 Correct 848 ms 87652 KB Output is correct
24 Correct 540 ms 56532 KB Output is correct
25 Correct 1261 ms 84268 KB Output is correct
26 Correct 1292 ms 81964 KB Output is correct
27 Correct 1069 ms 79044 KB Output is correct
28 Correct 21 ms 23800 KB Output is correct
29 Correct 20 ms 23800 KB Output is correct
30 Correct 21 ms 23800 KB Output is correct
31 Correct 20 ms 23800 KB Output is correct
32 Correct 21 ms 23800 KB Output is correct
33 Correct 40 ms 27640 KB Output is correct
34 Correct 20 ms 23800 KB Output is correct
35 Correct 19 ms 23800 KB Output is correct
36 Correct 20 ms 23800 KB Output is correct
37 Incorrect 21 ms 23800 KB Output isn't correct
38 Halted 0 ms 0 KB -