Submission #219277

#	Time	Username	Problem	Language	Result	Execution time	Memory
219277		yayups	Dreaming (IOI13_dreaming)	C++11	0 / 100	113 ms	65540 KiB

dreaming

// created 01 FEB 2018
// updated JUNE 2018
// updated JULY 2018
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <map>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <bitset>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <list>
#include <stdexcept>
#include "dreaming.h"

using namespace std;

vector<vector<int> > adjlist;
vector<vector<int> > adjlist_weight;
vector<int> comps;
vector<int> depth;
vector<int> depth1;



int label(int v, int c) {
	if(comps[v]!=-1) return 0;
	comps[v]=c;
	for(int i=0;i<(int)adjlist[v].size();i++) {
		label(adjlist[v][i],c);
	}
	return 1;
}

int label_dist(int v, int d) {
	if(depth[v]!=-1) return 0;
	depth[v]=d;
	for(int i=0;i<(int)adjlist[v].size();i++) {
		label_dist(adjlist[v][i],d+adjlist_weight[v][i]);
	}
	return 1;
}

int label_dist1(int v, int d) {
	if(depth1[v]!=-1) return 0;
	depth1[v]=d;
	for(int i=0;i<(int)adjlist[v].size();i++) {
		label_dist1(adjlist[v][i],d+adjlist_weight[v][i]);
	}
	return 1;
}




int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	vector<int> temp;
	adjlist.clear();
	adjlist_weight.clear();
	for(int i=0;i<N;i++) {
		temp.clear();
		adjlist.push_back(temp);
		adjlist_weight.push_back(temp);
		comps.push_back(-1);
	}
	for(int i=0;i<M;i++) {
		adjlist[A[i]].push_back(B[i]);
		adjlist[B[i]].push_back(A[i]);
		
		adjlist_weight[A[i]].push_back(T[i]);
		adjlist_weight[B[i]].push_back(T[i]);
	}
	/*for(int i=0;i<N;i++) {
		cout << i << ": ";
		for(int j=0;j<adjlist[i].size();j++) {
			cout << adjlist[i][j] << " ";
		}
		cout << endl;
	}*/
	
	/*vector<pair<int,int> > leaf; //first is weight, second is i
	pair<int,int> p;
	for(int i=0;i<N;i++) {
		if(adjlist[i].size()==1) {
			p.first=adjlist_weight[i][0];
			p.second=i;
			leaf.push_back(p);
		}
		if(adjlist[i].size()==0) {
			p.first=0;
			p.second=i;
			leaf.push_back(p);
		}
	}
	sort(leaf.begin(),leaf.end());
	for(int i=0;i<leaf.size();i++) {
		cout << "leaf is at " << leaf[i].second << endl;
	}*/
	
	
	int c=0;
	for(int v=0;v<N;v++) {
		if(label(v,c)==1) c++;
	}
	/*for(int i=0;i<N;i++) {
		cout << i << ": " << comps[i] << endl;
	}*/
	vector<int> center(c);
	vector<int> center1(c);
	vector<int> hba(N,0); //is 1 if i has been added at some point in past
	vector<queue<int> > bfs;
	queue<int> ttemp;
	//if(not ttemp.empty()) cout << "WHAT";
	for(int i=0;i<c;i++) bfs.push_back(ttemp);
	
	for(int i=0;i<N;i++) {
		if(adjlist[i].size()==1 or adjlist[i].size()==0) {
			bfs[comps[i]].push(i);
			hba[i]=1;
		}
	}
	//cout << bfs[0].front() << endl;
	//now we do bfs
	int k=-10;
	for(int i=0;i<c;i++) {
		ttemp=bfs[i];
		k=-10;
		//cout << ttemp.front() << endl;
		while(ttemp.size()>1)  {
			k=ttemp.front();
			ttemp.pop();
			for(int j=0;j<(int)adjlist[k].size();j++) {
				if(hba[adjlist[k][j]]==1) continue;
				hba[adjlist[k][j]]=1;
				ttemp.push(adjlist[k][j]);
			}
		}
		center[i]=ttemp.front();
		if(k!=-10) center1[i]=k;
		else center1[i]=ttemp.front();
	}
	/*for(int i=0;i<c;i++) {
		cout << "color " << i << " has center " << center[i] << endl;
	}*/
	//now we find radii
	vector<int> radii(c,0);
	vector<int> radii1(c,0);
	vector<int> far(c);
	for(int i=0;i<N;i++) {
		depth.push_back(-1);
	}
	for(int i=0;i<c;i++) {
		label_dist(center[i],0);
	}
	for(int i=0;i<N;i++) {
		if(depth[i]>radii[comps[i]]) {
			radii[comps[i]]=depth[i];
			far[comps[i]]=i;
		}
	}
	for(int i=0;i<N;i++) {
		depth1.push_back(-1);
	}
	for(int i=0;i<c;i++) {
		label_dist1(center1[i],0);
	}
	for(int i=0;i<N;i++) {
		if(depth1[i]>radii1[comps[i]]) radii1[comps[i]]=depth1[i];
	}
	/*for(int i=0;i<N;i++) {
		cout << i << ": depth = " << comps[i] << endl;
	}*/
	/*for(int i=0;i<c;i++) {
		cout << "color " << i << " has radius " << radii[i] << endl;
	}*/
	/*for(int i=0;i<c;i++) {
		cout << "color " << i << " has radius " << radii1[i] << endl;
	}*/
	for(int i=0;i<c;i++) {
		radii[i]=min(radii[i],radii1[i]);
	}
	/*for(int i=0;i<c;i++) {
		cout << "color " << i << " has radius " << radii[i] << endl;
	}*/
	
	vector<int> diam(c,0);
	depth1.clear();
	for(int i=0;i<N;i++) {
		depth1.push_back(-1);
	}
	for(int i=0;i<c;i++) {
		label_dist1(far[i],0);
	}
	for(int i=0;i<N;i++) {
		if(depth1[i]>diam[comps[i]]) diam[comps[i]]=depth1[i];
	}
	
	/*for(int i=0;i<c;i++) {
		cout << "color " << i << " has diam " << diam[i] << endl;
	}*/
	
	int maxdiam=0;
	for(int i=0;i<c;i++) {
		if(diam[i]>maxdiam) maxdiam=diam[i];
	}
	
	sort(radii.begin(),radii.end());
	
	if(c==1) return maxdiam;
	if(c==2) {
		return max(maxdiam,radii[c-1]+radii[c-2]+L);
	}
	if(c>=3) {
		int tempans=max(maxdiam,radii[c-1]+radii[c-2]+L);
		return max(tempans,2*L+radii[c-2]+radii[c-3]);
	}
	return 42;
}

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