init.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <cctype>

using namespace std;

class Trie
{
public:
	int i;
	string s;
	
	Trie* parent;
	map<char, Trie*> children;
	
	
	
	
	Trie(int nI, Trie* nParent = NULL) : i(nI), parent(nParent)
	{
	}
	
	~Trie()
	{
		for (map<char, Trie*>::iterator it = children.begin(); it != children.end(); ++it)
			delete it->second;
	}
	
	void insert(int nI, string nS)
	{		
		//cout << "inserting " << nI << " " << nS << endl;
		if (children.empty())
		{
			if (i == -1)
			{
				i = nI;
				s = nS;
				return;
			}
			else
			{
				Trie* child = new Trie(i, this);
				if (s.empty())
				{
					child->s = "";
					children[' '] = child;
				}
				else
				{
					child->s = s.substr(1);
					children[s[0]] = child;
				}
				
				i = -1;
				s.clear();
			}
		}
		
		if (nS.empty())
		{
			Trie* child = new Trie(nI, this);
			child->s = "";
			children[' '] = child;
		}
		else if (children.find(nS[0]) != children.end())
		{
			children[nS[0]]->insert(nI, nS.substr(1));
		}
		else
		{
			Trie* child = new Trie(nI, this);
			child->s = nS.substr(1);
			children[nS[0]] = child;
		}
		
	}
	
	void print(int d = 0)
	{
		if (i != -1)
		{
			cout << string(d, ' ') << i << " " << s << endl;
		}
		
		
		for (map<char, Trie*>::iterator it = children.begin(); it != children.end(); ++it)
		{
			cout << string(d, ' ') << it->first << ": " << endl; 
			it->second->print(d + 1);
		}
	}
	
	void getInits(map<int, string>& inits, string init)
	{
		if (i != -1)
		{
			inits[i] = init;
		}
		
		
		for (map<char, Trie*>::iterator it = children.begin(); it != children.end(); ++it)
		{
			init += it->first;
			it->second->getInits(inits, init);
			init.erase(init.size() - 1);
		}
	}
};

int main()
{
	ifstream fin("init.sis");
	ofstream fout("init.val");
	
	int N;
	fin >> N;
	
	Trie* root = new Trie(-1);
	vector<string> nimed;
	
	for (int n = 0; n < N; n++)
	{
		string ees, pere;
		fin >> ees >> pere;
		
		string s;
		s += ees[0];
		s += pere;
		for (string::iterator it = s.begin(); it != s.end(); ++it)
			*it = tolower(*it);
		
		nimed.push_back(s);
		
		
		
		root->insert(n, s);
		/*cout << string(80, '-') << endl;
		cout << "==" << s << endl;
		root->print();*/
	}
	/*cout << string(80, '=') << endl;
	root->print();*/
	
	map<int, string> inits;
	root->getInits(inits, "");
	
	for (map<int, string>::iterator it = inits.begin(); it != inits.end(); ++it)
	{
		if (it->second.size() < 2)
			it->second = nimed[it->first].substr(0, 2);
		fout << it->second << endl;
	}
	
	delete root;
	return 0;
}

loge.cpp

#include <iostream>
#include <fstream>
#include <set>
#include <map>

using namespace std;

int main()
{
	ifstream fin("loge.sis");
	ofstream fout("loge.val");
	
	int N;
	fin >> N;
	
	map<int, int> times;
	map<int, int> starts;
	map<int, int> sessions;
	
	int prevT = -1;
	for (int n = 0; n < N; n++)
	{
		int t, sid, uid;
		char ev;
		fin >> t >> ev >> sid >> uid;
		
		switch (ev)
		{
		case 'S':
			sessions[uid]++;
			if (starts.find(uid) == starts.end())
				starts[uid] = t;
			break;
		case 'V':
		{
			if (--sessions[uid] == 0)
			{
				times[uid] += t - starts[uid];
				starts.erase(starts.find(uid));
			}
			break;
		}
		case 'R':
			for (map<int, int>::iterator it = starts.begin(); it != starts.end(); ++it)
				times[it->first] += t - it->second;
			starts.clear();
			sessions.clear();
			break;
		}
		
		prevT = t;
	}
	
	// finish all ongoing at end
	for (map<int, int>::iterator it = starts.begin(); it != starts.end(); ++it)
		times[it->first] += prevT - it->second;
	
	for (map<int, int>::iterator it = times.begin(); it != times.end(); ++it)
		fout << it->first << " " << it->second << endl;
	return 0;
}

side.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int getmaster(vector<int>& masters, int i)
{
	int j = i;
	
	do
	{
		j = masters[j];
	}
	while (j != masters[j]);
	
	masters[i] = j;
	return j;
}

struct Proposal
{
	int A, B, C;
	int k;
};

bool operator< (const Proposal& lhs, const Proposal& rhs)
{
	return lhs.C < rhs.C;
}

int main()
{
	ifstream fin("side.sis");
	ofstream fout("side.val");
	
	int N, M, K;
	fin >> N >> M >> K;
	
	vector<int> masters; // disjoint set
	for (int n = 0; n < N; n++)
		masters.push_back(n);
	
	int nSets = N;
	
	for (int m = 0; m < M; m++)
	{
		int A, B;
		fin >> A >> B;
		A--; B--;
		if (getmaster(masters, A) != getmaster(masters, B))
		{
			masters[getmaster(masters, B)] = getmaster(masters, A);
			nSets--;
		}
	}
	
	vector<Proposal> proposals;
	for (int k = 0; k < K; k++)
	{
		Proposal p;
		fin >> p.A >> p.B >> p.C;
		p.A--; p.B--;
		p.k = k;
		proposals.push_back(p);
	}
	sort(proposals.begin(), proposals.end());
	
	/*for (int i = 0; i < proposals.size(); i++)
		cout << proposals[i].C << " " << proposals[i].k << " " << proposals[i].A << "-" << proposals[i].B << endl;*/
	
	
	vector<int> taken;
	int totalC = 0;
	for (vector<Proposal>::iterator it = proposals.begin(); it != proposals.end() && nSets > 1; ++it)
	{
		if (getmaster(masters, it->A) != getmaster(masters, it->B))
		{
			masters[getmaster(masters, it->B)] = getmaster(masters, it->A);
			nSets--;
			taken.push_back(it->k);
			totalC += it->C;
		}
	}
	
	fout << totalC << " " << taken.size() << endl;
	for (unsigned int i = 0; i < taken.size(); i++)
		fout << taken[i] + 1 << " ";
	fout << endl;
	
	
	return 0;
}