oj.uz

답안 #418845

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
418845 2021-06-06T05:01:12 Z cpp219 이상적인 도시 (IOI12_city) C++14
100 / 100
 65 ms 13416 KB 
#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

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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5708 KB Output is correct
2 Correct 4 ms 5668 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 4 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 4 ms 5708 KB Output is correct
7 Correct 4 ms 5708 KB Output is correct
8 Correct 4 ms 5708 KB Output is correct
9 Correct 4 ms 5708 KB Output is correct
10 Correct 4 ms 5708 KB Output is correct
11 Correct 4 ms 5708 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 4 ms 5836 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 5 ms 5872 KB Output is correct
5 Correct 6 ms 5836 KB Output is correct
6 Correct 5 ms 5836 KB Output is correct
7 Correct 6 ms 5836 KB Output is correct
8 Correct 5 ms 5836 KB Output is correct
9 Correct 5 ms 5836 KB Output is correct
10 Correct 5 ms 5788 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 6296 KB Output is correct
2 Correct 12 ms 6472 KB Output is correct
3 Correct 26 ms 7388 KB Output is correct
4 Correct 25 ms 7232 KB Output is correct
5 Correct 47 ms 8724 KB Output is correct
6 Correct 47 ms 8632 KB Output is correct
7 Correct 47 ms 8956 KB Output is correct
8 Correct 49 ms 8640 KB Output is correct
9 Correct 49 ms 8984 KB Output is correct
10 Correct 50 ms 13416 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 6984 KB Output is correct
2 Correct 14 ms 6924 KB Output is correct
3 Correct 33 ms 9112 KB Output is correct
4 Correct 29 ms 8348 KB Output is correct
5 Correct 65 ms 12344 KB Output is correct
6 Correct 52 ms 10152 KB Output is correct
7 Correct 64 ms 12412 KB Output is correct
8 Correct 53 ms 10212 KB Output is correct
9 Correct 53 ms 9724 KB Output is correct
10 Correct 51 ms 9536 KB Output is correct