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;
}

 464 total views,  2 views today

Leave a Reply

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