KirillLykov’s gists

KirillLykov / cf_333_d2_b.cpp

Last active January 26, 2018 20:51

codeforces 333, div2 b

	// Kinda long solution
	// Complexity - nlogn
	#include <bits/stdc++.h>
	using namespace std;

	int getLargestAConst(const vector<int>& a) {
	int maxL = 0;
	int l = 0, r = 0;
	map<int, int> subseq;
	while (r != a.size()) {

KirillLykov / sumAllPathGraph.cpp

Last active February 1, 2018 14:20

Compute the sum of pathes between any pairs of vertices in not oriented, connected graph with number of edges equal to number of vertices - 1.

	/*
	The problem is taken from https://www.e-olymp.com/en/problems/2157
	*/
	#include <bits/stdc++.h>
	using namespace std;
	typedef long long int lint;
	lint mod = 1e9;

	vector<list<int>> adj;
	vector<bool> visited;

KirillLykov / cf_div2_177_d.cpp

Created February 5, 2018 10:14

codeforces div2 177 d

KirillLykov / cf_intel_elem.cpp

Created February 20, 2018 21:43

Solution for "Intel Code Challenge Elimination Round (Div. 1 + Div. 2, combined)" Problem C, Destruction of Array

	/*
	Solution for "Intel Code Challenge Elimination Round (Div. 1 + Div. 2, combined)"
	Problem C, Destruction of Array
	http://codeforces.com/contest/722/problem/C

	I used modified DisjointSet (additionally stores sum of elements in connected component)
	Bitmask to check neighbors
	*/
	#include <bits/stdc++.h>
	using namespace std;

KirillLykov / cf_spb_15.cpp

Last active March 12, 2018 20:14

Useful hash string problem

	// http://codeforces.com/gym/100126/attachments/download/1321/20122013-tryenirovka-spbgu-b-15-heshi-ru.pdf
	// Problem A
	#include <bits/stdc++.h>
	using namespace std;
	typedef long long int lint;
	typedef long double ldouble;

	const lint p = 307;
	const lint M = lint(1e9) + 7;

KirillLykov / cf_g.cpp

Last active February 28, 2018 17:24

	//http://codeforces.com/gym/100371/attachments/download/2258/2014-zimnyaya-shkola-po-programmirovaniu-harkov-dyen-1-ye-kapun-vysshaya-liga-ru.pdf
	#include <bits/stdc++.h>
	using namespace std;
	typedef long long int lint;
	typedef long double ldouble;

	typedef pair<lint, int> E;
	int n;
	vector<vector<E>> adj; // weight, vtx
	vector< vector<int> > parents;

KirillLykov / cf_revgraph.cpp

Created March 11, 2018 21:57

solution for http://codeforces.com/gym/220829/problem/B

	// Solution for http://codeforces.com/gym/220829/problem/B
	//
	#include <bits/stdc++.h>
	using namespace std;
	typedef long long int lint;
	typedef long double ldouble;

	typedef pair<int, int> E;
	int n;
	vector<vector<int>> adj, revadj;

KirillLykov / cf_ed_36_f.cpp

Created March 12, 2018 20:50

solution for educational round of codeforces 36, problem F

	/*
	Solution for educational round 36, F
	http://codeforces.com/problemset/problem/915/F
	I used modified DisjointSet (additionally stores size of set)
	*/
	#include <bits/stdc++.h>
	using namespace std;
	typedef long long int lint;

	class disjoint_sets

KirillLykov / cf_vk17_1_c.cpp

Last active March 13, 2018 22:37

solution for CF VK Cup 2017, round 1, problem C

	// solution for CF VK Cup 2017, round 1, problem C
	// http://codeforces.com/contest/769/problem/C
	// The idea:
	// Front step) we go greedy until it is possible to go back from the current cell
	// This check is done by the help of shortest distance matrix d
	// Back step) Find the lexigocraphically optimal backward path following distance matrix d
	#include <bits/stdc++.h>
	using namespace std;
	typedef long long int lint;
	typedef long double ldouble;

KirillLykov / cf_197_d2_d.cpp

Created March 25, 2018 18:42

solution for codeforces 197, div2, d using a-la segment tree

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long int lint;
	typedef long double ldouble;

	const int N = 1<<17 + 1;
	int a[N];
	int t[4*N];
	void build(int cur, int L, int R, int level) {
	if (L == R) { // level == 0

kirill lykov KirillLykov