제출 #418845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
418845		cpp219	이상적인 도시 (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;
}

컴파일 시 표준 에러 (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