[Tutorial][GYM] 2018 AICCSA Programming Contest

Some problems don't have a tutorial yet, those should be added later.

Tutorial is loading...

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const N = 1000000;
int dpfr[2][N + 1], dp[N + 1], n, gr[N + 1];
vector<int> tr[N + 1];

vector<int> cn;
int getcn(int v = 1, int p = 0){
	bool ok = true;
	int s = 1;
	f(i, 0, tr[v].size()){
		int u = tr[v][i];
		if (u == p)continue;
		int t = getcn(u, v);
		if (t > n >> 1)ok = false;
		s += t;
	}
	if (n - s > n >> 1)ok = false;
	if (ok)cn.push_back(v);
	return s;
}

int G;
void pl(int v, int p = 0){
	dp[v] = dp[p] + 1;
	gr[v] = G;
	f(i, 0, tr[v].size()){
		int u = tr[v][i];
		if (u == p)continue;
		pl(u, v);
	}
}

ll P(int x) { return (ll)x * (x - 1) >> 1; }

void solve(){
	scanf("%d", &n);
	f(i, 1, n + 1)tr[i].clear();
	f(j, 0, 2)f(i, 1, n + 1)dpfr[j][i] = 0;
	f(i, 2, n + 1){
		int t;
		scanf("%d", &t);
		tr[i].push_back(t);
		tr[t].push_back(i);
	}
	cn.clear();
	getcn();
	ll an = P(n);
	if ((int)cn.size() == 1){
		pl(cn[0]);
		f(i, 1, n + 1)++dpfr[0][dp[i]];
		f(i, 1, n + 1)an += P(dpfr[0][i]);
	}else {
		G = 0;
		dp[cn[1]] = 0;
		pl(cn[0], cn[1]);
		G = 1;
		dp[cn[0]] = 0;
		pl(cn[1], cn[0]);
		dp[cn[0]] = 1;
		f(i, 1, n + 1)++dpfr[gr[i]][dp[i]];
		f(i, 1, n + 1){
			an += P(dpfr[0][i]);
			an += P(dpfr[1][i]);
			an -= (ll)dpfr[0][i] * dpfr[1][i];
		}
	}
	printf("%lld\n", an);
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--)solve();
}

Tutorial is loading...

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const N = 200000, md = 1e9 + 7;
int x[N], y[N], fc[N + 1], xt[N + 1], yt[N + 1];

void solve(){
	int n;
	scanf("%d", &n);
	n <<= 1;
	f(i, 0, n)scanf("%d%d", x + i, y + i);
	f(i, 0, n)xt[i] = x[i];
	sort(xt, xt + n);
	f(i, 0, n)yt[i] = y[i];
	sort(yt, yt + n);
	n >>= 1;
	if (xt[n - 1] == xt[n]) { printf("0\n"); return; }
	if (yt[n - 1] == yt[n]) { printf("0\n"); return; }
	n <<= 1;
	int a = 0, b = 0;
	f(i, 0, n)if (x[i] < xt[n >> 1])y[i] < yt[n >> 1] ? ++a : ++b;
	int an = (ll)fc[a] * fc[b] % md;
	printf("%d\n", an);
}

int main(){
	fc[0] = 1;
	f(i, 1, N + 1)fc[i] = (ll)fc[i - 1] * i % md;
	int t;
	scanf("%d", &t);
	while (t--)solve();
}

Tutorial is loading...

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const N = 1000000, md = 1e9 + 7;
int fc[N + 1], inv[N + 1], fcin[N + 1];

void ad(int &x, int y) { if ((x += y) >= md)x -= md; }
void sb(int &x, int y) { if ((x -= y) < 0)x += md; }
int ch(int n, int r) { return (ll)fc[n] * fcin[r] % md * fcin[n - r] % md; }

void solve(){
	int n;
	scanf("%d", &n);
	int s = 0, an = 0;
	f(i, 0, n){
		ad(s, ch(n, i + 1));
		int t;
		scanf("%d", &t);
		ad(an, (ll)t * s % md);
		sb(s, ch(n, i));
	}
	printf("%d\n", an);
}

int main(){
	fc[0] = 1;
	f(i, 1, N + 1)fc[i] = (ll)fc[i - 1] * i % md;
	inv[1] = 1;
	f(i, 2, N + 1)inv[i] = md - md / i * (ll)inv[md % i] % md;
	fcin[0] = 1;
	f(i, 1, N + 1)fcin[i] = (ll)fcin[i - 1] * inv[i] % md;
	int t;
	scanf("%d", &t);
	while (t--)solve();
}

Tutorial is loading...

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
const int M = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
const int oo = 1000000000;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define pb push_back 
#define all(c) (c).begin(),(c).end()
int T,n,k;
multiset<int> A,B;

int main(){
	cin>>T;
	while(T--){
		A.clear();
		B.clear();
		cin>>n>>k;
		for(int x,i=0; i<n; ++i){
			scanf("%d",&x);
			A.insert(x);
		}
		for(int x,i=0; i<n; ++i){
			scanf("%d",&x);
			if(A.find(x)!=A.end())
				A.erase(A.find(x));
			else
				B.insert(x);
		}
		if(A.empty())
			puts("YES");
		else if(A.size()==1 && B.size()==1 && abs(*A.begin()-*B.begin())<=k)
			puts("YES");
		else
			puts("NO");
		
	}
	return 0;	
}

Tutorial is loading...

Short and precise explanation by TooDumbToWin can be found here.

Code1

//#pragma comment(linker, "/STACK:16777216")

#include <stdio.h>
#include <iostream>
#include <vector>
#include <assert.h>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <sstream>
#include <memory.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100000;
int n, res;
vector<vector<int> > g, o, v;
vector<vector<vector<int> > > cyc;
set<pair<int, int> > br;
int low[N], idx[N], dfs;
bool vis[N];
void DFS(int u, int p) {
	low[u] = idx[u] = ++dfs;
	for (auto v : g[u])
		if (!idx[v]) {
			DFS(v, u);
			low[u] = min(low[u], low[v]);
			if (low[v] > idx[u])
				br.insert({ min(u,v),max(u,v) });
		}
		else if (v != p)
			low[u] = min(low[u], idx[v]);
}
void DFS(int u) {
	if (vis[u])
		return;
	v.back().push_back(u);
	vis[u] = true;
	for (auto &w : g[u])
		DFS(w);
}
vector<vector<int> > options;
void findOptions(int u, int p) {
	if (g[u].size() > 3 && vis[u]) {
		if (options.back()[0] == options.back().back())
			options.back().pop_back();
		return;
	}
	if (p != -1 && g[u].size() == 3)
		return;
	vis[u] = true;
	for (auto v : g[u])
		if (v != p) {
			if (p == -1) {
				if (vis[v])
					continue;
				options.push_back(vector<int>());
				options.back().push_back(u);
			}
			options.back().push_back(v);
			findOptions(v, u);
		}
}
void findCycles(vector<int> &comp, vector<vector<int> > &cyc) {
	for (int i = 0; i < n; ++i)
		vis[i] = 0;
	for (auto u : comp) {
		if (vis[u])
			continue;
		cyc.push_back(vector<int>());
		queue<int> q;
		q.push(u);
		vis[u] = true;
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			cyc.back().push_back(u);
			for (auto v : g[u])
				if (!vis[v]) {
					vis[v] = true;
					q.push(v);
				}
		}
		if (cyc.back().size() == 1)
			cyc.pop_back();
	}
	if (cyc.size() == 1) {
		int at = -1;
		for (auto x : cyc[0])
			if (g[x].size() == 4) {
				at = x;
				break;
			}
		if (at != -1) {
			for (int i = 0; i < n; ++i)
				vis[i] = 0;
			options.clear();
			findOptions(at, -1);
			assert(options.size() == 2);
			cyc = options;
		}
	}
	assert(cyc.size() <= 2);
}
int findClosest(const vector<int> &v, int x) {
	int idx = lower_bound(v.begin(), v.end(), x) - v.begin();
	int cur = 1e9;
	if (idx != v.size())
		cur = v[idx] - x;
	if (idx != 0)
		cur = min(cur, x - v[idx - 1]);
	return cur;
}
int calc(int u, int p) {
	int ret = findClosest(cyc[0][0], u);
	for (auto v : g[u])
		if (v != p && br.find({ min(u,v),max(u,v) }) != br.end())
			ret = min(ret, calc(v, u));
	res = min(res, ret + findClosest(v[1], u));
	return ret;
}
int main()
{
	int t;
	scanf("%d", &t);
	int totalN=0;
	while (t--) {
		scanf("%d", &n);
		totalN+=n;
		g.clear();
		g.resize(n);
		if (n < 1 || n>100000) {
			puts("invalid n");
			exit(1);
		}
		set<pair<int, int> > e;
		for (int i = 1, a, b; i < n; ++i) {
			scanf("%d%d", &a, &b);
			if (a<1 || a>n || b<1 || b>n) {
				puts("Invalid (a, b)");
				exit(2);
			}
			if (a > b)
				swap(a, b);
			if (e.insert({ a,b }).second == false) {
				puts("Multiple edges");
				exit(3);
			}
			--a; --b;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		for (int i = 0; i < n; ++i)
			vis[i] = 0;
		for (int i = 0; i < n; ++i)
			idx[i] = 0;
		dfs = 0;
		v.clear();
		cyc.clear();
		for (int i = 0; i < n; ++i)
			if (!vis[i]) {
				v.push_back(vector<int>());
				if (v.size() == 4)
					break;
				DFS(i);
			}
		if (v.size() == 4) {
			puts("-1");
			continue;
		}
		if (v.size() == 1) {
			puts("0");
			continue;
		}
		br.clear();
		for (int i = 0; i < n; ++i)
			if (!idx[i])
				DFS(i, -1);
		o = g;
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < g[i].size(); ++j)
				if (br.find({ min(i,g[i][j]),max(i,g[i][j]) }) != br.end()) {
					g[i][j] = g[i].back();
					g[i].pop_back();
					--j;
				}
		cyc.resize(v.size());
		for (int i = 0; i < v.size(); ++i)
			findCycles(v[i], cyc[i]);
		for (auto &cycles : cyc)
			for (auto &x : cycles) {
				sort(x.begin(), x.end());
				assert(x.size() >= 3);
			}
		res = 1e9;
		if (v.size() == 2) {
			if (cyc[0].empty()) {
				v[0].swap(v[1]);
				cyc[0].swap(cyc[1]);
			}
			sort(v[1].begin(), v[1].end());
			g = o;
			for (auto x : cyc[0][0])
				calc(x, -1);
			printf("%d\n", res);
			continue;
		}
		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < 2; ++j)
				if (cyc[j].size() < cyc[j + 1].size()) {
					v[j].swap(v[j + 1]);
					cyc[j].swap(cyc[j + 1]);
				}
		if (cyc[0].size() == 2) {
			pair<int, int> A(1e9, 1e9), B(1e9, 1e9);
			for (int it = 1; it <= 2; ++it) {
				for (int i = 0; i < v[it].size(); ++i) {
					A.first = min(A.first, findClosest(cyc[0][0], v[it][i]));
					A.second = min(A.second, findClosest(cyc[0][1], v[it][i]));
				}
				swap(A, B);
			}
			res = min(A.first + B.second, A.second + B.first);
			printf("%d\n", res);
			continue;
		}
		if (!cyc[1].empty()) {
			for (int i = 0; i < 2; ++i) {
				int curA = 1e9;
				for (auto x : v[2])
					curA = min(curA, findClosest(cyc[i][0], x));
				int curB = 1e9;
				for (auto x : v[2])
					curB = min(curB, findClosest(cyc[!i][0], x));
				for (auto x : v[i])
					curB = min(curB, findClosest(cyc[!i][0], x));
				res = min(res, curA + curB);
			}
			printf("%d\n", res);
			continue;
		}
		options.clear();
		for (int i = 0; i < n; ++i)
			vis[i] = 0;
		for (auto u : cyc[0][0])
			if (g[u].size() > 2) {
				findOptions(u, -1);
				break;
			}
		assert(options.size() == 3);
		for (auto &x : options)
			sort(x.begin(), x.end());
		int cur[2][3] = {};
		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < 3; ++j) {
				cur[i][j] = 1e9;
				for (auto x : v[i + 1])
					cur[i][j] = min(cur[i][j], findClosest(options[j], x));
			}
		for (int i = 0; i < 3; ++i) {
			res = min(res, cur[0][i] + min(cur[1][!i], cur[1][3 - i - !i]));
			res = min(res, cur[1][i] + min(cur[0][!i], cur[0][3 - i - !i]));
		}
		printf("%d\n", res);
	}
	cerr<<totalN<<endl;
	assert(totalN<=5000000);
	return 0;
}

Code2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
typedef vector<pair<int, int> > vp;

int const N = 100000, inf = 1e9;
vp g[N + 1];
vector<int> cy[N];
int vis[N + 1], vs = 1, n;

struct CM{
	vector<set<int> > v;
	set<int> all;
	CM(){}
	bool operator <(CM const &o)const { return v.size() > o.v.size(); }
	bool in(int x) { return all.find(x) != all.end(); }
};

bool in(int x, set<int> const &st) { return st.find(x) != st.end(); }

int getCost(int x, set<int> const &st){
	set<int>::iterator it = st.lower_bound(x);
	int an = it == st.end() ? inf : *it - x;
	if (it == st.begin())return an;
	--it;
	return min(an, x - *it);
}

int getCost(set<int> const &a, set<int> const &b){
	int an = inf;
	set<int>::iterator ita = a.begin(), itb = b.begin();
	while (ita != a.end() && itb != b.end()){
		an = min(an, abs(*ita - *itb));
		if (*ita < *itb)++ita; else ++itb;
	}
	return an;
}

vector<CM> cm;
map<vector<int>, int> mp;

int getId(vector<int> const &v){
	map<vector<int>, int>::iterator it = mp.find(v);
	if (it == mp.end()){
		int an = mp.size();
		cm.back().v.push_back(set<int>());
		return mp[v] = an;
	}
	return it->second;
}

int C;
vp build(int v, int p = 0){
	vp c;
	vis[v] = 0;
	f(i, 0, g[v].size()){
		int u = g[v][i].first;
		if (u == p)continue;
		if (vis[u] == 0)c.push_back(make_pair(C, u)), cy[g[v][i].second].push_back(C++);
		else {
			vp t = build(u, v);
			while (t.size())c.push_back(t.back()), cy[g[v][i].second].push_back(t.back().first), t.pop_back();
		}
	}
	f(i, 0, c.size())if (c[i].second == v)c.erase(c.begin() + i), --i;
	vis[v] = 1;
	return c;
}

void geted(int v){
	vis[v] = 0;
	cm.back().all.insert(v);
	f(i, 0, g[v].size()){
		int u = g[v][i].first;
		int id = g[v][i].second;
		if (!cy[id].empty()){
			sort(cy[id].begin(), cy[id].end());
			int cid = getId(cy[id]);
			cm.back().v[cid].insert(v);
			cm.back().v[cid].insert(u);
			cy[id].clear();
		}
		if (vis[u] == 0)continue;
		geted(u);
	}
}

void visi(int v){
	if (vis[v] == vs)return;
	vis[v] = vs;
	f(i, 0, g[v].size())visi(g[v][i].first);
}

int go(int v, int p, int mn = inf){
	int an = mn + getCost(v, cm[0].v[0]);
	mn = min(mn, getCost(v, cm[1].all));
	f(i, 0, g[v].size()){
		int u = g[v][i].first;
		if (u == p)continue;
		an = min(an, go(u, v, mn));
	}
	return an;
}

int solve(){
	scanf("%d", &n);
	f(i, 1, n + 1)g[i].clear();
	f(i, 1, n)cy[i].clear();
	f(i, 1, n){
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].push_back(make_pair(b, i));
		g[b].push_back(make_pair(a, i));
	}
	int cmp = 0;
	f(i, 1, n + 1)vis[i] = inf;
	f(i, 1, n + 1)if (vis[i] > vs)++vs, visi(i), ++cmp;
	if (cmp == 1)return 0;
	if (cmp > 3)return -1;
	cm.clear();
	f(i, 1, n + 1)if (vis[i] > 1){
		cm.push_back(CM());
		mp.clear();
		build(i);
		geted(i);
	}
	sort(cm.begin(), cm.end());
	int an = inf;
	if (cmp == 2){
		an = getCost(cm[0].v[0], cm[1].all);
		f(i, 1, n + 1)if (in(i, cm[0].v[0]))f(j, 0, g[i].size())if (!in(g[i][j].first, cm[0].v[0]))an = min(an, go(g[i][j].first, i));
		return an;
	}
	if (cm[0].v.size() > 1){
		f(i, 0, cm[0].v.size())f(j, 0, cm[0].v.size())if (i != j)an = min(an, getCost(cm[0].v[i], cm[1].all) + getCost(cm[0].v[j], cm[2].all));
		return an;
	}
	int a = getCost(cm[0].v[0], cm[1].all);
	int b = getCost(cm[0].v[0], cm[2].all);
	int c = getCost(cm[1].v[0], cm[0].all);
	int d = getCost(cm[1].v[0], cm[2].all);
	return min(b + min(c, d), d + min(a, b));
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--)printf("%d\n", solve());
}

Tutorial is loading...

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const N = 200000;
double const eps = 1e-7;
int n, a, q;
long double an[N];

bool eq(double a, double b) { return abs(a - b) <= eps; }

struct V{
	double x, y;
	V(double a = 0.0, double b = 0.0):x(a), y(b) {}
	void sc() { scanf("%lf%lf", &x, &y); }
	double operator |(V const &o)const {
		return x * o.y - o.x * y;
	}
	bool operator <(V const &o)const {
		if (eq(x, o.x))return y < o.y;
		return x < o.x;
	}
	V operator -(V const &o)const { return V(x - o.x, y - o.y); }
	void pr() { printf("%lf %lf\n", x, y); }
}st[N];

pair<V, int> qu[N];

bool cmpr(V const &a, V const &b){
	V v1 = a - st[0], v2 = b - st[0];
	return (v1 | v2) < -eps;
}	


vector<V> ch;
void getCh(){
	sort(st + 1, st + n, cmpr);
	ch.push_back(st[0]);
	f(i, 1, n){
		while ((int)ch.size() > 1 && (st[i] - ch.back() | ch.back() - ch[ch.size() - 2]) < eps)ch.pop_back();
		ch.push_back(st[i]);
	}
}

double getx(double xs, double z, double xq){
	return xs + z / (z + a) * (xq - xs);
}

int left(int x) { return x ? x - 1 : ch.size() - 1; }
int right(int x) { return x + 1 == (int)ch.size() ? 0 : x + 1; }

void solve(){
	scanf("%d%d", &n, &a);
	f(i, 0, n)st[i].sc();
	double mnz = st[0].y, mxz = st[0].y;
	f(i, 1, n){
		mnz = min(mnz, st[i].y);
		mxz = max(mxz, st[i].y);
	}
	f(i, 0, n)st[i].y = a - st[i].y;
	sort(st, st + n);
	ch.clear();
	getCh();
	scanf("%d", &q);
	f(i, 0, q){
		qu[i].first.sc();
		qu[i].second = i;
	}
	sort(qu, qu + q);
	int lp = 0, rp = 0;
	f(i, 0, ch.size())ch[i].y = a - ch[i].y;
	while (ch[right(rp)].y < ch[rp].y)rp = right(rp);
	while (ch[left(lp)].y > ch[lp].y)lp = left(lp);
	f(i, 0, q){
		while (true){
			int ni = right(lp);
			if (getx(ch[ni].x, ch[ni].y, qu[i].first.x) < getx(ch[lp].x, ch[lp].y, qu[i].first.x))lp = ni;
			else break;
		}
		while (true){
			int ni = right(rp);
			if (getx(ch[ni].x, ch[ni].y, qu[i].first.x) > getx(ch[rp].x, ch[rp].y, qu[i].first.x))rp = ni;
			else break;
		}
		double x = abs(getx(ch[rp].x, ch[rp].y, qu[i].first.x) - getx(ch[lp].x, ch[lp].y, qu[i].first.x));
		double y = getx(0, mxz, qu[i].first.y) - getx(0, mnz, qu[i].first.y);
		an[qu[i].second] = (long double) x * y;;
	}
	f(i, 0, q)printf("%.10lf\n", (double)an[i]);
}

int main(){
	int t;
	scanf("%d", &t);
	while (t--)solve();
}

Tutorial is loading...

Code

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
typedef pair<int,int> pii;
typedef long long ll;
const int N = 10000+1;

int n , q,T;
vector<pii> g[N];
ll ans = 0,in[N],out[N];

void dfs(int u , int p, int w){
	for(auto v : g[u]){
		if(v.first==p)continue;
		dfs(v.first,u,v.second);
		in[u] += in[v.first];
		out[u] += out[v.first];
	}
	ans += 1ll*abs(in[u]-out[u])*w;
}
int main(){
	cin >> T;
	while(T--){
		cin >> n;
		ans = 0;
		for (int i = 1; i <= n; ++i){
			g[i].clear();
			in[i] = out[i] = 0;
		}
		for (int u , v,w , i = 0 ; i < n-1 ; ++i){
			scanf("%d%d%d",&u,&v,&w);
			g[u].pb(mp(v,w));
			g[v].pb(mp(u,w));
		}
		cin >> q;
		for(int u , v , i = 0 ; i < q ; ++i){
			scanf("%d%d",&u,&v);
			out[u]++;
			in[v]++;
		}
		dfs(1,-1,0);
		cout << ans << endl;
	}

	return 0;
}

Tutorial is loading...

Code

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
const int N = 1001;
int n , l , dp[N][N],T;

pii a[N];

int calc(int idx , int time){
	if(idx > n || time > l+1)return -N;
	if(idx == n && time == l+1)return 0;
	int &ret = dp[idx][time];
	if(ret != -1)return ret;
	ret = max(calc(idx,time+1),calc(idx+1,time));
	if(time >= a[idx].first)
		ret = max(ret,1+calc(idx+1,time+a[idx].second));
	return ret;
}
int main(){
	cin >> T;
	while(T--){
		memset(dp,-1,sizeof dp);
		cin >> n >> l;
		for (int i = 0; i < n; ++i)scanf("%d%d",&a[i].first,&a[i].second);
		printf("%d\n",calc(0,1));
	}

	return 0;
}

Tutorial is loading...

Code

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
int n , m , r,T;

vector< vector<int> > g;
multiset< pii > hv[100002];
multiset<pii> cur;

int
 ALL_PEOPLE = 0;
bool check(int md){
	cur.clear();
	for(int i = 0 ; i < m ; ++i)hv[i].clear();
	for(int j = 0 ; j < md ; ++j)cur.insert(make_pair(-2,m));

	for(int j = 0 ; j < n ; ++j){
		for (int i = 0; i < m; ++i){
			int rem = g[i][j];
			vector<int> nw;
			while(rem > 0){
				assert(cur.size() == md);
				if(hv[i].size()){
					pii fr = *--hv[i].end();
					hv[i].erase(--hv[i].end());
					cur.erase(cur.find(fr));
					cur.insert(make_pair(j,i));
					nw.push_back(j);
				}else{
					pii em = *cur.begin();
					if(em.first >= j-1)return false;
					cur.erase(cur.begin());
					if(em.second != m)
						hv[em.second].erase(hv[em.second].find(em));
					cur.insert(make_pair(j,i));
					nw.push_back(j);
				}
				rem -= r;
			}
			for(int k = 0 ; k < nw.size();++k){
				hv[i].insert(make_pair(nw[k],i));
			}
		}
	}
	return 1;
}

int main(){
//	freopen("2.in","r",stdin);
//	freopen("2.out","w",stdout);
	cin >> T;
	while(T--){
		scanf("%d%d%d",&m,&n,&r);
		g.clear();
		g.resize(m);
		int total = 0;
		for (int i = 0; i < m; ++i){
			g[i].resize(n);
			for(int j = 0 ; j < n ; ++j){
				scanf("%d",&g[i][j]);
				total += g[i][j];
			}
		}
		ALL_PEOPLE += total;
		int lo = 1, hi = total,best = -1;
		while(lo <= hi){
			int md = (lo + hi)/2;
			if(check(md)){
				best = md;
				hi = md-1;
			}else{
				lo=md+1;
			}
		}
		cout << best << endl;
	}
	//cout << "ALL PEOPLE = " << ALL_PEOPLE << endl;

	return 0;
}

Tutorial is loading...

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
const int M = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
const int oo = 1000000000;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
#define pb push_back 
#define all(c) (c).begin(),(c).end()
int n,m,cmp[2*N],t;
vi g[2*N],rg[2*N];
bool vis[2*N];

int Not(int x){
	return x>=n?x-n:x+n;
}

void addEdge(int a, int b){
	g[Not(b)].pb(a);
	g[Not(a)].pb(b);
	rg[a].pb(Not(b));
	rg[b].pb(Not(a));
}

stack<int> st;
void dfs(int u, vi g[N], int cc=-1){
	vis[u]=1;
	for(int i=0; i<g[u].size(); ++i)
		if(!vis[g[u][i]])
			dfs(g[u][i], g, cc);
	if(cc==-1){
		st.push(u);
	}else{
		cmp[u]=cc;
	}
}

void get(int &x, int l, int r){
	assert(scanf("%d",&x)==1);
	assert(x>=l && x<=r);
}

int main(){
	get(t,1,1000);
	while(t--){
		get(n, 1, 100000);
		get(m, 0, 100000);
		for(int a,b,c,i=0; i<m; ++i){
			get(a,1,n);
			get(b,1,n);
			assert(a!=b);
			get(c,0,1);
			--a;--b;
			if(c)
				addEdge(Not(a), Not(b));
			addEdge(a, b);
		}
		for(int i=0; i<2*n; ++i)
			vis[i]=0;
		for(int i=0; i<2*n; ++i)
			if(!vis[i])
				dfs(i,g);
		for(int i=0; i<2*n; ++i)
			vis[i]=0;
		int cc=0;
		while(!st.empty()){
			int u=st.top();
			st.pop();
			if(vis[u])continue;
			dfs(u, rg, cc++);
		}
		bool win=1;
		for(int i=0; i<n && win; ++i){
			if(cmp[i]==cmp[Not(i)])
				win=0;
		}
		if(win)
			puts("YES");
		else
			puts("NO");

		for(int i=0; i<2*n; ++i){
			g[i].clear();
			rg[i].clear();
		}
	}
	return 0;	
}

Comments (13)

Show archived | Write comment?

collares

5 years ago, # |

← Rev. 2 →

+16

So, just to confirm: The rectangle (mirror) in problem F must be axis-aligned, right? Is it possible to add that to the problem statement?

→ Reply

Motarack

5 years ago, # ^ |

+24

Yes, I will do that, sorry for the confusion.

+19

No worries. Thanks for the nice contest!

wa007

Could you share a solution code for problem A ? I can't debug my code....thanks

Added above.

vatsal

Is anyone of these problems intended for Div2 guys?

As mentioned in the announcement the contest is intended for contestants with rating in the range [1600, 2600].

Gr8

For Problem D. Two Sequences Why this code is giving WA as verdict on Test Case 2:

vector<long>v1(n+1),v2(n+1);
    REP(i,n){
       cin>>v1[i];
    }
    REP(i,n){
       cin>>v2[i];
    }
            bool flag = 1;
    REP(i,n){
       long x = v1[i], y = v2[i];
       if(abs(x-y)<=k)   flag &= 1;
       else  {flag = 0;break;}
    }

    if(flag == 0)  cout<<"NO\n";
    else cout<<"YES\n";

make sure to read the statement correctly, if you still don't know why it's wrong then try manually some random small cases.

Shafin_Ahmed

Problem C (Bonus):

Coefficient of $$$a_k = \frac{(k+1)\binom{n+1}{k+1}}{n-k+1}-1$$$ will do the trick.

TShT

4 years ago, # ^ |

How could this be noticed? All my attempts to calculate or guess the formula were not correct

2ndSequence

4 years ago, # |

Can anyone provide how to solve G?

Tutorial updated

#	User	Rating
1	ecnerwala	3650
2	Benq	3582
3	Geothermal	3570
3	orzdevinwang	3570
5	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3532
8	Radewoosh	3522
9	Um_nik	3483
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Motarack's blog