Submission #274841

#	Time	Username	Problem	Language	Result	Execution time	Memory
274841		shayan_p	Ideal city (IOI12_city)	C++14	100 / 100	531 ms	14824 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;
const int Nine = (int)1e9;

vector<int> v[maxn];

int pr[maxn];

int fnd(int u){
    return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
bool mrg(int a, int b){
    if( (a = fnd(a)) == (b = fnd(b)) )
	return 0;
    if(pr[a] > pr[b])
	swap(a, b);
    pr[a]+= pr[b];
    pr[b] = a;
    return 1;
}
int SZ[maxn];
int dfs(int tot, int u, int par = -1){
    int ans = 0;
    SZ[u] = -pr[fnd(u)];
    for(int y : v[u]){
	if(y != par){
	    ans = (ans + dfs(tot, y, u)) % Nine;
	    SZ[u]+= SZ[y];
	}
    }
    ans = (1ll * ans + 1ll * SZ[u] * (tot - SZ[u])) % Nine;
    return ans;
}
void add_edge(int a, int b){
    v[a].PB(b);
    v[b].PB(a);
}
int solve(int n, int *X, int *Y){
    for(int i = 0; i < n; i++){
	v[i].clear();
    }
    
    memset(pr, -1, sizeof pr);
    
    map<pii, int> mp;
    for(int i = 0; i < n; i++)
	mp[{X[i], Y[i]}] = i;
    vector<int> vc;    
    for(int i = 0; i < n; i++){
	if(mp.count({X[i], Y[i]+1}))
	    mrg(i, mp[{X[i], Y[i]+1}]);	
    }
    for(int i = 0; i < n; i++){
	if(mp.count({X[i]+1, Y[i]}))
	    vc.PB(i);
    }
    sort(vc.begin(), vc.end(), [&](int i, int j){ return Y[i] < Y[j]; });
    for(int a : vc){
	int b = mp[{X[a]+1, Y[a]}];
	if(mp.count({X[a], Y[a]+1}) == 0 || mp.count({X[a]+1, Y[a]+1}) == 0)
	    add_edge(fnd(a), fnd(b));
    }
    return dfs(n, fnd(0));
}
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: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45