Submission #144633

#	Time	Username	Problem	Language	Result	Execution time	Memory
144633		gs18115	Ideal city (IOI12_city)	C++14	100 / 100	106 ms	16184 KiB

city

#include<vector>
#include<algorithm>
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const ll inf=1e18;
const ll mod=1e9;
vector<int>adj[100010];
ll ans;
int sz[100010];
int s2[100010];
ll dp[100010];
void dfs(int x,int p)
{
    sz[x]=s2[x];
    for(int t:adj[x])
    {
        if(t==p)
            continue;
        dfs(t,x);
        sz[x]+=sz[t];
    }
    dp[x]=sz[x];
    for(int t:adj[x])
        if(t!=p)
            ans=(ans+dp[t]*(sz[x]-sz[t]))%mod,dp[x]+=dp[t];
    return;
}
inline void solv(vector<pl>&p)
{
    int n=p.size();
    int i;
    int cnt=0;
    vector<int>ind;
    ind.eb(cnt);
    sort(all(p));
    for(i=1;i<n;i++)
    {
        if(p[i].fi==p[i-1].fi&&p[i].se==p[i-1].se+1)
            ind.eb(cnt);
        else
            ind.eb(++cnt);
    }
    cnt++;
    for(i=0;i<cnt;i++)
        s2[i]=0;
    for(i=0;i<cnt;i++)
        adj[i].clear();
    for(i=0;i<n;i++)
        s2[ind[i]]++;
    vector<pair<pl,int> >P;
    for(i=0;i<n;i++)
        P.eb(pl(p[i].se,p[i].fi),ind[i]);
    sort(all(P));
    for(i=1;i<n;i++)
    {
        pl&t=P[i].fi;
        pl&s=P[i-1].fi;
        if(t.fi==s.fi&&t.se==s.se+1)
        {
            adj[P[i].se].eb(P[i-1].se);
            adj[P[i-1].se].eb(P[i].se);
        }
    }
    for(i=0;i<=cnt;i++)
    {
        sort(all(adj[i]));
        adj[i].erase(unique(all(adj[i])),adj[i].end());
    }
    dfs(0,-1);
    return;
}
int DistanceSum(int N,int*X,int*Y)
{
    vector<pl>P;
    int i;
    for(i=0;i<N;i++)
        P.eb(X[i],Y[i]);
    solv(P);
    P.clear();
    for(i=0;i<N;i++)
        P.eb(Y[i],X[i]);
    solv(P);
    return ans;
}

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