Submission #211150

#	Time	Username	Problem	Language	Result	Execution time	Memory
211150		junodeveloper	Ideal city (IOI12_city)	C++17	100 / 100	693 ms	17380 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;
template<int mod>
struct modint{
	int v;
	modint(ll vv=0){s(vv%mod+mod);}
	modint& s(int vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	modint operator-()const{return modint()-*this;}
	modint& operator+=(const modint&rhs){return s(v+rhs.v);}
	modint&operator-=(const modint&rhs){return s(v+mod-rhs.v);}
	modint&operator*=(const modint&rhs){
		v=ll(v)*rhs.v%mod;
		return *this;
	}
	modint&operator/=(const modint&rhs){return *this*=rhs.inv();}
	modint operator+(const modint&rhs)const{return modint(*this)+=rhs;}
	modint operator-(const modint&rhs)const{return modint(*this)-=rhs;}
	modint operator*(const modint&rhs)const{return modint(*this)*=rhs;}
	modint operator/(const modint&rhs)const{return modint(*this)/=rhs;}
	modint pow(int n)const{
		modint res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	modint inv()const{return pow(mod-2);}
	/*modint inv()const{
		int x,y;
		int g=egcd(v,mod,x,y);
		assert(g==1);
		if(x<0)x+=mod;
		return modint(x);
	}*/
	friend modint operator+(int x,const modint&y){return modint(x)+y;}
	friend modint operator-(int x,const modint&y){return modint(x)-y;}
	friend modint operator*(int x,const modint&y){return modint(x)*y;}
	friend modint operator/(int x,const modint&y){return modint(x)/y;}
	friend ostream& operator<<(ostream&os,const modint&m){return os<<m.v;}
	friend istream& operator>>(istream&is,modint&m){
		ll x;is>>x;
		m=modint(x);
		return is;
	}
	bool operator<(const modint&r)const{return v<r.v;}
	bool operator==(const modint&r)const{return v==r.v;}
	bool operator!=(const modint&r)const{return v!=r.v;}
	explicit operator bool()const{return v;}
};
using mint=modint<mod>;
int n;
pii p[100010];
map<pii,int> mem;
vi g[100010];
int par[100010],cnt[100010];
mint 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);
	if(a==b)return;
	par[b]=a;
	cnt[a]+=cnt[b];
}
void dfs(int p,int u,int dep) {
	make_unique(g[u]);
	mint ds=0,ss=0;
	for(auto& it:g[u]) {
		if(it==p)continue;
		dfs(u,it,dep+1);
		tot+=(ds-dep*ss)*sub[it]+(dp[it]-dep*sub[it])*ss;
		ds+=dp[it];
		ss+=sub[it];
	}
	tot+=(ds-dep*ss)*cnt[u];
	dp[u]=ds+dep*cnt[u];
	sub[u]=ss+cnt[u];
}
mint solve() {
	tot=0;
	mem.clear();
	rep(i,n){
		par[i]=i;
		cnt[i]=1;
		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){
		dfs(i,i,0);
		break;
	}
	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];
	mint ans=solve();
	rep(i,n){ 
		swap(p[i].fi,p[i].se);p[i].fi*=-1;
	}
	ans+=solve();
	return ans.v;
}

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: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45