Submission #1034385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034385		idas	Ideal city (IOI12_city)	C++11	100 / 100	114 ms	35536 KiB

city

#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int MxN=1e5+10, mod=1e9;
ll cn[MxN][2], dp[MxN][2]; // how many nodes in group
map<pii, int> gr[2];
set<int> ad[MxN][2];

void build(int u, int k, int pst=-1)
{
//    cout << k << " -> " << u << '\n';
//    for(auto it : ad[u][k]){
//        cout << it << " ";
//    }
//    cout << '\n';

    dp[u][k]=cn[u][k];
    for(auto it : ad[u][k]){
        if(it==pst) continue;
        build(it, k, u);
        dp[u][k]+=dp[it][k];
    }
}

ll ans=0;
void dfs(int u, int k, ll up=0, int pst=-1)
{
    ans+=up*dp[u][k]%mod;
    ans%=mod;

    for(auto it : ad[u][k]){
        if(it==pst) continue;
        dfs(it, k, up+dp[u][k]-dp[it][k], u);
    }
}

int DistanceSum(int n, int x[], int y[]) {
    vector<pii> inf;
    FOR(i, 0, n)
    {
        inf.pb({x[i],y[i]});
    }
    sort(inf.begin(), inf.end());

    int now;
    FOR(k, 0, 2)
    {
//        cout << k << ":\n";
//        FOR(i, 0, n)
//        {
//            cout << inf[i].f << " " << inf[i].s << '\n';
//        }

        FOR(i, 0, n)
        {
            if(i==0 || inf[i-1].f!=inf[i].f || inf[i-1].s+1!=inf[i].s) now=i;

            int a=inf[i].f, b=inf[i].s;
            gr[k][{a,b}]=now;
            cn[now][k]++;

            if(gr[k].count({a-1,b})){
                int nxt=gr[k][{a-1,b}];
                ad[now][k].insert(nxt);
                ad[nxt][k].insert(now);
            }
        }

        build(0, k);
        dfs(0, k);

        FOR(i, 0, n) swap(inf[i].f, inf[i].s);
        sort(inf.begin(), inf.end());
    }

    return ans;
}

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