Submission #211131

#	Time	Username	Problem	Language	Result	Execution time	Memory
211131		junodeveloper	Ideal city (IOI12_city)	C++14	0 / 100	233 ms	9380 KiB

city

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define mset(x,y) memset(x,y,sizeof(x))
#define rep(i,n) for(int i=0;i<int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef LOCAL
#define dmp(...) _dmp(#__VA_ARGS__, __VA_ARGS__)
#else
#define dmp(...) (__VA_ARGS__)
#endif
template<class T> using vt=vector<T>;
template<class T> using vvt=vt<vt<T>>;
template<class TA,class TB> void chmax(TA&a,TB b){if(a<b)a=b;}
template<class TA,class TB> void chmin(TA&a,TB b){if(b<a)a=b;}
template<class TA,class TB>
ostream& operator<<(ostream& os,const pair<TA,TB>& p){
	return os<<"{"<<p.fi<<","<<p.se<<"}";
}
template<class T> ostream& operator<<(ostream& os,const vt<T>& v){
	os<<"{";for(auto& e:v)os<<e<<",";return os<<"}";
}
template<class TH> void _dmp(const char *sdbg, TH h){cout<<sdbg<<"="<<h<<endl;}
template<class TH, class... TA> void _dmp(const char *sdbg, TH h, TA...a){
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
}
template<class T> void make_unique(vt<T>& v) {
	sort(all(v));v.erase(unique(all(v)),v.end());
}
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
int ri(){int x;cin>>x;return x;}
ll rll(){ll x;cin>>x;return x;}
vi rvi(int n){vi v;rep(i,n)v.pb(ri());return v;}
const int mod=1e9;
int n;
pii p[100010];
map<pii,int> mem;
vi g[100010];
int par[100010],xl[100010],xr[100010];
int dp[100010],sub[100010],tot;
int pn(int u){return u==par[u]?u:(par[u]=pn(par[u]));}
void us(int a,int b){
	a=pn(a),b=pn(b);
	par[b]=a;
	xl[a]=min(xl[a],xl[b]);
	xr[a]=max(xr[a],xr[b]);
}
void dfs(int p,int u,int dep) {
	int ds=0,ss=0;
	for(auto& it:g[u]) {
		if(it==p)continue;
		dfs(u,it,dep+1);
		tot+=(ll)(dp[it]-(ll)dep*sub[it]%mod+mod)%mod*(xr[u]-xl[u]+1)%mod;
		tot%=mod;
		tot+=((ds-(ll)dep*ss%mod+mod)%mod*sub[it]%mod+(dp[it]-(ll)dep*sub[it]%mod+mod)%mod*ss%mod)%mod;
		tot%=mod;
		ds+=dp[it];ds%=mod;
		ss+=sub[it];
	}
	dp[u]=(ds+(ll)dep*(xr[u]-xl[u]+1)%mod)%mod;
	sub[u]=ss+xr[u]-xl[u]+1;
}
int solve() {
	tot=0;
	mem.clear();
	rep(i,n){
		par[i]=i;
		xl[i]=xr[i]=p[i].fi;
		g[i].clear();
		mem[p[i]]=i;
	}
	rep(i,n) {
		if(mem.count(mp(p[i].fi-1,p[i].se)))
			us(i,mem[mp(p[i].fi-1,p[i].se)]);
		if(mem.count(mp(p[i].fi+1,p[i].se)))
			us(i,mem[mp(p[i].fi+1,p[i].se)]);
	}
	rep(i,n) {
		if(mem.count(mp(p[i].fi,p[i].se-1)))
			g[pn(i)].pb(pn(mem[mp(p[i].fi,p[i].se-1)]));
		if(mem.count(mp(p[i].fi,p[i].se+1)))
			g[pn(i)].pb(pn(mem[mp(p[i].fi,p[i].se+1)]));
	}
	rep(i,n)if(par[i]==i)make_unique(g[i]);
	dfs(0,0,0);
	return tot;
}
int DistanceSum(int N, int *X, int *Y) {
	n=N;
	rep(i,n)p[i].se=Y[i],p[i].fi=X[i];
	int ans=solve();
	rep(i,n)swap(p[i].fi,p[i].se);
	ans+=solve();ans%=mod;
	return ans;
}

Compilation message (stderr)

city.cpp: In function 'void _dmp(const char*, TH, TA ...)':
city.cpp:36:1: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
 while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
 ^~~~~
city.cpp:36:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
 while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
                                ^~~~

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