APIO 2018 Problems and Solutions

APIO 2018 Problems and Solutions

The official APIO 2018 Problems and solutions in this post.

Problems :

statements-en

Solution – A (New Home) :

#include <bits/stdc++.h
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 300005;
 
struct query{
	int pos, t, idx;
	bool operator<(const query &q)const{
		return t < q.t;
	};
}qry[MAXN];
 
struct query2{
	int t, mode, val;
	bool operator<(const query2 &q)const{
		return pi(t, mode) < pi(q.t, q.mode);
	};
};
 
struct rect{ int st, et, y, mode, rpos; };
// mode 1 : [0, y]
// mode -1 : [y, inf]
struct intv{ int s, e, x; };
vector<intv> house[MAXN];
vector<rect> rec;
int n, k, q, ans[MAXN];
const int inf = 500000005;
 
struct rect2{
	int sx, ex, ins;
	bool operator<(const rect2 &r)const{
		return sx < r.sx;
	}
};
 
void process(int h){
	vector<query2> v;
	for(auto &i : house[h]){
		i.s = lower_bound(qry, qry + q, (query){-1, i.s, -1}) - qry;
		i.e = upper_bound(qry, qry + q, (query){-1, i.e, -1}) - qry;
		if(i.s == i.e) continue;
		v.push_back({i.s, 1, i.x});
		v.push_back({i.e, -1, i.x});
	}
	sort(v.begin(), v.end());
	map<int, int> cnt;
	set<rect2> r;
	r.insert({-1, inf, 0});
	auto insert_rect = [&](int st, int et, int sy, int ey){
		if(st == et) return;
		et--;
		if(sy == -1){
			rec.push_back({st, et, -1, -1, ey});
			return;
		}
		if(ey == inf){
			rec.push_back({st, et, inf, 1, sy});
			return;
		}
		int my = (sy + ey) / 2;
		rec.push_back({st, et, my, 1, sy});
		rec.push_back({st, et, my+1, -1, ey});
	};
	for(int i=0; i<v.size(); i++){
		auto insert_intv = [&](int pos){
			auto l = --r.upper_bound({pos, -1, -1});
			insert_rect(l->ins, v[i].t, l->sx, l->ex);
			rect2 ins1 = {l->sx, pos, v[i].t};
			rect2 ins2 = {pos, l->ex, v[i].t};
			r.erase(l);
			r.insert(ins1);
			r.insert(ins2);
		};
		auto remove_intv = [&](int pos){
			auto nxt = r.lower_bound({pos, -1, -1});
			auto prv = prev(nxt);
			insert_rect(prv->ins, v[i].t, prv->sx, prv->ex);
			insert_rect(nxt->ins, v[i].t, nxt->sx, nxt->ex);
			rect2 ins = {prv->sx, nxt->ex, v[i].t};
			r.erase(prv);
			r.erase(nxt);
			r.insert(ins);
		};
		for(int j=i; j<i+1; j++){
			if(cnt[v[j].val] == 0) insert_intv(v[j].val);
			cnt[v[j].val] += v[j].mode;
			if(cnt[v[j].val] == 0) remove_intv(v[j].val);
		}
	}
}
 
struct query3{
	int pos, l, r, v;
	bool operator<(const query3 &q)const{
		return pos < q.pos;
	}
};
 
vector<query3> mode1,mode2;
// mode1 : disappear after y + 1
// mode2 : appear after y
 
struct seg{
	int seg[1050000], lim;
	void init(int n){
		for(lim = 1; lim <= n; lim <<= 1);
		fill(seg, seg + 1050000, 1e9);
	}
	void add(int l, int r, int val){
		l += lim;
		r += lim;
		while(l < r){
			if(l%2 == 1) seg[l] = min(seg[l], val), l++;
			if(r%2 == 0) seg[r] = min(seg[r], val), r--;
			l >>= 1;
			r >>= 1;
		}
		if(l == r) seg[l] = min(seg[l], val);
	}
	int query(int pos){
		pos += lim;
		int ans = 1e9;
		while(pos){
			ans = min(ans, seg[pos]);
			pos >>= 1;
		}
		return ans;
	}
}seg;
 
int main(){
	scanf("%d %d %d",&n,&k,&q);
	for(int i=0; i<n; i++){
		int x, t, s, e;
		x = rand()%100000000 + 1;
		t = rand()%k +1;
		s = 1;
		e = 100000000;
		scanf("%d %d %d %d",&x,&t,&s,&e);
		house[t].push_back({s, e, x});
	}
	for(int i=1; i<=k; i++){
		house[i].push_back({1, 100000000, 500000000});
	}
	for(int i=0; i<q; i++){
		qry[i].pos = rand()%100000000 + 1;
		qry[i].t = 1;
		scanf("%d %d",&qry[i].pos,&qry[i].t);
		qry[i].idx = i;
	}
	sort(qry, qry + q);
	for(int i=1; i<=k; i++) process(i);
	for(auto &j : rec){
		if(j.mode == 1){
			mode1.push_back({j.y, j.st, j.et, j.rpos});
		}
		else{
			mode2.push_back({j.y, j.st, j.et, j.rpos});
		}
	}
	for(int i=0; i<q; i++) qry[i].t = i;
	sort(qry, qry + q, [&](const query &a, const query &b){
		return a.pos < b.pos;
	});
	sort(mode1.begin(), mode1.end());
	sort(mode2.begin(), mode2.end());
	int ptr = 0;
	seg.init(q + 1);
	for(int i=0; i<q; i++){
		while(ptr < mode2.size() && mode2[ptr].pos <= qry[i].pos){
			seg.add(mode2[ptr].l, mode2[ptr].r, -mode2[ptr].v);
			ptr++;
		}
		int query2 = -seg.query(qry[i].t) - qry[i].pos;
		ans[qry[i].idx] = max(ans[qry[i].idx], query2);
	}
	seg.init(q + 1);
	ptr = mode1.size();
	for(int i=q-1; i>=0; i--){
		while(ptr > 0 && mode1[ptr-1].pos >= qry[i].pos){
			ptr--;
			seg.add(mode1[ptr].l, mode1[ptr].r, mode1[ptr].v);
		}
		int query1 = qry[i].pos - seg.query(qry[i].t);
		ans[qry[i].idx] = max(ans[qry[i].idx], query1);
	}
	for(int i=0; i<q; i++){
		if(ans[i] > 2e8) ans[i] = -1;
		printf("%d\n", ans[i]);
	}
}

Solution – B (Circle Selection) :

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
const int offs = 1e9 + 100;
using pi = pair<int, int>;

struct circ{
	int x, y, r, idx;
	bool operator<(const circ &c)const{
		return pi(x, y) < pi(c.x, c.y);
	}
}a[MAXN], orig_pos[MAXN];

int n, ans[MAXN];

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].r);
		a[i].x += offs;
		a[i].y += offs;
		a[i].idx = i + 1;
		orig_pos[i + 1] = a[i];
	}
	auto inter = [&](circ a, circ b){
		int dx = a.x - b.x;
		int dy = a.y - b.y;
		int dr = a.r + b.r;
		return 1ll * dx * dx + 1ll * dy * dy <= 1ll * dr * dr;
	};
	sort(a, a+n, [&](const circ &a, const circ &b){
		return pi(-a.r, a.idx) < pi(-b.r, b.idx);
	});
	for(int i=30; i; i--){
		int lb = (1 << (i - 1)), rb = (1 << i) - 1;
		vector<circ> v;
		for(int j=0; j<n; j++){
			if(!ans[a[j].idx] && a[j].r <= rb){
				v.push_back((circ){a[j].x >> i, a[j].y >> i, a[j].r, a[j].idx});
			}
		}
		sort(v.begin(), v.end());
		for(int j=0; j<n; j++){
			if(!ans[a[j].idx] && a[j].r <= rb && a[j].r >= lb){
				for(int k=-2; k<=2; k++){
					int px = (a[j].x >> i) + k;
					int py = (a[j].y >> i) - 2;
					auto itr = lower_bound(v.begin(), v.end(), (circ){px, py, -1, -1}) - v.begin();
					while(itr < v.size() && pi(v[itr].x, v[itr].y) <= pi(px, py + 4)){
						if(inter(orig_pos[v[itr].idx], a[j])){
							if(!ans[v[itr].idx]) ans[v[itr].idx] = a[j].idx;
						}
						itr++;
					}
				}
			}
		}
	}
	for(int i=1; i<=n; i++) printf("%d ", ans[i]);
}

Solution – C (Duathlon) :

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 100005;
 
int n, m;
int dfn[MAXN], low[MAXN], piv, col, vcnt;
vector<int> gph[MAXN];
vector<int> bcc[MAXN], cmp[MAXN];
 
void dfs(int x, int p){
    dfn[x] = low[x] = ++piv;
    vcnt++;
    for(auto &i : gph[x]){
        if(i == p) continue;
        if(!dfn[i]){
            dfs(i, x);
            low[x] = min(low[x], low[i]);
        }
        else low[x] = min(low[x], dfn[i]);
    }
}
 
void color(int x, int c){
    if(c){
        cmp[x].push_back(c);
        bcc.push_back(x);
    }
    for(auto &i : gph[x]){
        if(cmp[i].size()) continue;
        if(low[i] >= dfn[x]){
            col++;
            cmp[x].push_back(col);
            bcc[col].push_back(x);
            color(i, col);
        }
        else{
            color(i, c);
        }
    }
}
 
lint sameOrigin = 0;
lint diffOrigin = 0;
 
lint help(vector<int> &v){
    lint ret = accumulate(v.begin(), v.end(), 0ll);
    ret *= ret;
    for(auto &i : v) ret -= 1ll * i * i;
    return ret;
}
 
int solve(int x){
    int sum = 0;
    vector<int> circomp;
    for(int i=1; i<bcc[x].size(); i++){
        int csum = 0;
        int v = bcc[x][i];
        vector<int> vcomp;
        for(auto &j : cmp[v]){
            if(x == j) continue;
            int val = solve(j);
            vcomp.push_back(val);
            csum += val;
        }
        diffOrigin += help(vcomp);
        circomp.push_back(csum);
        sameOrigin -= 2ll * csum * (bcc[x].size() - 2);
        sum += csum + 1;
    }
    for(int i=0; i<circomp.size(); i++){
        int tmp = sum - bcc[x].size() + 1;
        diffOrigin += 2 * (tmp - circomp[i]);
    }
    diffOrigin += help(circomp);
    circomp.push_back(vcnt - sum);
    diffOrigin += 1ll * (bcc[x].size() - 1) * help(circomp);
    sameOrigin -= 1ll * (bcc[x].size() - 1) * (bcc[x].size() - 2) * (vcnt - bcc[x].size());
    return sum;
}
 
lint Do(int v){
    diffOrigin = sameOrigin = 0;
    vcnt = 0;
    dfs(v, 0);
    int pcol = col;
    color(v, 0);
    vector<int> seq = {1};
    for(int i=pcol + 1; i<=col;i++){
        seq.push_back(bcc[i].size() - 1);
    }
    int tot = accumulate(seq.begin(), seq.end(), 0);
    int pfx = 0;
    for(int i=0; i<seq.size(); i++){
        diffOrigin += 6ll * seq[i] * pfx * (tot - seq[i] - pfx);
        pfx += seq[i];
    }
    sameOrigin = 1ll * vcnt * (vcnt-1) * (vcnt-2) - diffOrigin;
    diffOrigin = 0;
    vector<int> w;
    for(auto &i : cmp[v]){
        w.push_back(solve(i));
    }
    diffOrigin += help(w);
    return diffOrigin + sameOrigin;
}
 
int main(){
    scanf("%d %d",&n,&m);
    for(int i=0; i<m; i++){
        int s, e;
        scanf("%d %d",&s,&e);
        gph[s].push_back(e);
        gph[e].push_back(s);
    }
    lint sum = 0;
    for(int i=1; i<=n; i++){
        if(!dfn[i]) sum += Do(i);
    }
    cout << sum << endl;
}

 57 total views,  2 views today

Post Disclaimer

The hole problem statement are given by  apio2018.ru but the solution are generated by the sltechnicalacademy authority if any of the query regarding this post or website fill the following contact form thank you. 

Leave a Reply

Your email address will not be published. Required fields are marked *