Submission #418845

#	Time	Username	Problem	Language	Result	Execution time	Memory
418845		cpp219	Ideal city (IOI12_city)	C++14	100 / 100	65 ms	13416 KiB

city

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e5 + 9;
const ll mod = 1e9;
typedef pair<ll,ll> LL;
ll dd[N],dp[N],cnt[N],sz[N],grp[N],n;
long long ans;
vector<LL> a;
set<ll> g[N];

void DFS(ll u){
    dd[u] = 1;
    for (auto i : g[u]){
        if (!dd[i]){
            DFS(i); sz[u] += sz[i];
        }
    }
    ans += 1ll * sz[u] * (n - sz[u]);
}

void solve(){
    memset(sz,0,sizeof(sz)); memset(dd,0,sizeof(dd));
    for (ll i = 0;i < n;i++) g[i].clear();
    sort(a.begin(),a.end());
    ll cnt = 0;
    for (ll i = 0;i < n;){
        ll j = i + 1; grp[i] = cnt;
        while (j < n && a[j] == make_pair(a[j - 1].fs,a[j - 1].sc + 1)) grp[j] = cnt,j++;
        sz[cnt] = j - i; cnt++;
        i = j;
    }
    ll j = 0;
    for (ll i = 0;i < n;i++){
        LL now = {a[i].fs - 1,a[i].sc};
        while(j < n&&a[j] < now) j++;
        if (j < n&&a[j] == now){
            g[grp[j]].insert(grp[i]);
            g[grp[i]].insert(grp[j]);
        }
    }
    DFS(0);
}

ll DistanceSum(ll N,ll *X,ll *Y){
    n = N;
    for (ll i = 0;i < N;i++) a.push_back({X[i],Y[i]});
    solve(); //cout<<ans; exit(0);
    for (ll i = 0;i < N;i++) swap(a[i].fs,a[i].sc);
    solve();
    return ans % mod;
}

Compilation message (stderr)

city.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
city.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      |

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