Submission #492084

#	Time	Username	Problem	Language	Result	Execution time	Memory
492084		robind3r	Dreaming (IOI13_dreaming)	C++17	0 / 100	174 ms	27272 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> to, sz;

//ez union find

int find(int x){
	if(x==to[x]) return x;
    return to[x] = find(to[x]);
}

void unite(int u, int v){
    int x = find(u);
    int y = find(v);
    if (x == y)
        return;
    if (sz[x] < sz[y])swap(x, y);
    sz[x]+=sz[y];
    to[y] = x;
}

bool same(int u, int v){
	return find(u) == find(v);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	//first step: find optimal point in which to add the new edge (for each component)
	//this can be done by starting from the bottom and finding the maximum from each side of the tree
	//we need to recursively find the nodes that only have one (zero?!) (unvisited) edge(s)
	//can probably be done with good time complexity but idk (i think it could become O(NlogN)? probably N squared done lazily)
	
	//from the input data we can easily create a vector<>[] representation as follows
	vector<pair<int, int>> node[N]; //node[a] = {b, w}
	vector<pair<int, int>> nodec[N]; //node[a] = {b, w}
	vector<pair<int, int>> noded[N]; //node[a] = {b, w}
	
	vector<tuple<int, int, int>> edges;
	
	int comp[N];
	bool visited[N];
	
	//epic dfs lambda
	function<void(int, int)> dfs = [&node, &comp, &dfs, &visited](int i, int n){
		if(visited[i])return;
		visited[i] = true;
		comp[i] = n;
		for(auto e : node[i])dfs(e.first, n);
	};
	
	for(int i = 0; i < M; i++){
		node[A[i]].push_back({B[i], T[i]});
		node[B[i]].push_back({A[i], T[i]});
		
		nodec[A[i]].push_back({B[i], T[i]});
		nodec[B[i]].push_back({A[i], T[i]});
		
		noded[A[i]].push_back({B[i], T[i]});
		noded[B[i]].push_back({A[i], T[i]});//it sets it 3 times because i was too lazy to let it copy later on in the code
		
		edges.push_back(make_tuple(A[i], B[i], T[i]));
		edges.push_back(make_tuple(B[i], A[i], T[i]));//for kruskal
	}
	
	//dfs to find the separate components
	for(int i = 0; i < N; i++)dfs(i, i);
	
	//next, we need to recursively find the tree "endings"
	//we just need to check if the number of edges coming in is 0...
	//we can probably do this for the whole tree with help from some array
	
	/*int numin[N];

	for(int i = 0; i < N; i++)numin[i] = 0;
	
	for(int i = 0; i < N; i++){
		for(auto e : node[i]){
			numin[e.first]++;
		}
	}*/
	
	vector<int> ord;
	
	while(true){
		for(int i = 0; i < N; i++){
			if(nodec[i].size() == 1){
				int il = 0;
				for (auto it : nodec[nodec[i][0].first]) {
					if(it.first==i)nodec[nodec[i][0].first].erase(nodec[nodec[i][0].first].begin() + il);
					il++;
    			}
    			ord.push_back(i);
    			if(ord.size()==N)goto el;
			}
		}
	}
	
	el:
	
	vector<int> maxer(N), fin(N, -1);
	
	for(int i = 0; i < N; i++){
		int t = ord[i];
		if(noded[t].size() == 1){
			if((maxer[t] + noded[t][0].second) > maxer[noded[t][0].first]){
				maxer[noded[t][0].first] = maxer[t] + noded[t][0].second;
				fin[comp[noded[t][0].first]] = noded[t][0].first;
			}
			int il = 0;
			for (auto it : noded[noded[t][0].first]) {
				if(it.first==t){
					noded[noded[t][0].first].erase(noded[noded[t][0].first].begin() + il);
				}
				il++;
    		}
		}
	}
	
	//ideally, the algorithm should be optimized to a better time complexity (finding the best vertex to connect can probably be done faster with the same idea)
	//for it to work with the whole input, the different slots should be permutated (maybe??? or Mst recalced every time???????)
	
	//let's complete (inaccurately) for M = N-2
	//join the two ideal vertices and then calculate the Mst
	
	int finq = -1;
	for(int i = 0; i < N; i++){
		if(finq==-1){
			if(fin[i]!=-1)finq = fin[i];
		}else{
			//assuming that M is equal to N-2
			edges.push_back(make_tuple(L, i, finq));
			edges.push_back(make_tuple(L, finq, i));
		}
	}
	
	//we now should theoretically have a fully connected graph of which we should find the maximum spanning tree
	//the solution to the problem will be equal to the final maximum spanning tree
	//we can easily implement the maximum spanning tree using a union-find structure
	
	sort(edges.rbegin(), edges.rend());
	to.resize(N);
	sz.resize(N, 0);
	iota(to.begin(), to.end(), 0);
	
	int tot = 0;
	for(auto e : edges){
		if(!same(get<1>(e), get<2>(e))){
			unite(get<1>(e), get<2>(e));
			tot+=get<0>(e);
		}
	}

    return tot;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:95:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |        if(ord.size()==N)goto el;
      |           ~~~~~~~~~~^~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23