Submission #274806

#	Time	Username	Problem	Language	Result	Execution time	Memory
274806		shayan_p	Ideal city (IOI12_city)	C++14	23 / 100	449 ms	9976 KiB

city

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
const int Nine = (int)1e9;

int arr[maxn];
pii scr[maxn];

int pr[maxn];

int fnd(int u){
    return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
void mrg(int a, int b){
    if( (a = fnd(a)) == (b = fnd(b)) )
	return;
    if(pr[a] > pr[b])
	swap(a, b);
    pr[a]+= pr[b];
    pr[b] = a;
}
int solve(int n, int *X, int *Y){
    int ans = 0;
    
    map<pii, int> mp;
    for(int i = 0; i < n; i++)
	mp[{X[i], Y[i]}] = i;
    auto cmp = [&](int i, int j){ return (pii){X[i], Y[i]} < (pii){X[j], Y[j]}; };
    iota(arr, arr + n, 0);
    sort(arr, arr + n, cmp);
    memset(pr, -1, sizeof pr);
    memset(scr, -1, sizeof scr);

    int pt = 0;
    while(pt < n){
	int ptl = pt, ptr = pt;
	while(ptr < n && X[arr[ptl]] == X[arr[ptr]])
	    ptr++;
	pt = ptr;
	for(int i = ptl; i < ptr; i++){
	    int x = X[arr[i]], y = Y[arr[i]];
	    for(pii p : { (pii){-1, 0}, (pii){0, 1}, (pii){0, -1} }){ // not x + 1
		int xx = x + p.F, yy = y + p.S;
		if(mp.count({xx, yy}))
		    mrg(arr[i], mp[{xx, yy}]);
	    }
	}
	for(int i = ptl; i < ptr; i++){
	    int x = X[arr[i]] + 1, y = Y[arr[i]];
	    if(mp.count({x, y}))
		scr[mp[{x, y}]] = {-pr[fnd(arr[i])], fnd(arr[i])};
	}
    }

    // Round 2
    {
	auto cmp = [&](int i, int j){ return (pii){-X[i], Y[i]} < (pii){-X[j], Y[j]}; };
	sort(arr, arr + n, cmp);
	memset(pr, -1, sizeof pr);
	
	int pt = 0;
	while(pt < n){
	    int ptl = pt, ptr = pt;
	    while(ptr < n && X[arr[ptl]] == X[arr[ptr]])
		ptr++;
	    pt = ptr;
	    for(int i = ptl; i < ptr; i++){
		int x = X[arr[i]], y = Y[arr[i]];
		for(pii p : { (pii){1, 0}, (pii){0, 1}, (pii){0, -1} }){ // not x - 1
		    int xx = x + p.F, yy = y + p.S;
		    if(mp.count({xx, yy}))
			mrg(arr[i], mp[{xx, yy}]);
		}
	    }
	    set<pii> st;
	    for(int i = ptl; i < ptr; i++){
		if(scr[ arr[i] ].F == -1)
		    continue;
		int A = fnd(arr[i]), B = scr[ arr[i] ].S;
		if(st.count({A, B}))
		    continue;
		st.insert({A, B});
		ans = (1ll * ans + 1ll * scr[ arr[i] ].F * (-pr[fnd(arr[i])])) % Nine;
	    }
	}
    }
    return ans;
}
int ITER = 0;
int DistanceSum(int n, int *X, int *Y){
    assert(++ITER <= 1);
    return (solve(n, X, Y) + solve(n, Y, X)) % Nine;
}
    

• Subtask 1: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 23 / 23
• Subtask 4: 0 / 45