oj.uz

Submission #97726

# Submission time Handle Problem Language Result Execution time Memory
97726 2019-02-17T19:27:10 Z TAMREF Ideal city (IOI12_city) C++11
100 / 100
 190 ms 21436 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define emp emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
using ll = long long;
using lf = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

const int mx = 1e5 + 5;
const ll mod = 1e9;
pii P[mx];
int n;
int rep[mx];
ll sz[mx], dep[mx];
ll ss[mx], sds[mx];
bool vis[mx];
vector<int> G[mx], C[mx];

int f(int x){
    return x == rep[x] ? x : rep[x] = f(rep[x]);
}

void c(int x, int y){
    x = f(x); y = f(y);
    if(x != y){
        rep[y] = x;
        sz[x] += sz[y];
    }
}

unordered_map<ll,int> S;

void dfsi(int x){
    vis[x] = 1;
    for(int u : G[x]){
        if(vis[u]) continue;
        C[x].push_back(u);
        dep[u] = dep[x] + 1;
        dfsi(u);
    }
}

ll dis;
void dfs(int x){
    ll SS = sz[x], SSQ = sz[x] * sz[x] % mod, SDS = sz[x] * dep[x] % mod, SDSQ = sz[x] * sz[x] * dep[x] % mod;
    for(int u : C[x]){
        dfs(u);
        SS += ss[u]; SS %= mod;
        SSQ += ss[u] * ss[u] % mod; SSQ %= mod;
        SDS += sds[u]; SDS %= mod;
        SDSQ += sds[u] * ss[u] % mod; SDSQ %= mod;
    }
    //printf("dfs on %d : ss = %lld, ssq = %lld, sds = %lld, sdsq = %lld\n",x,ss[x],ssq[x],sds[x],sdsq[x]);
    dis += SDS * SS % mod - SDSQ - dep[x] * (SS * SS % mod - SSQ) % mod;
    dis = (dis % mod + mod) % mod;
    ss[x] = SS;
    sds[x] = SDS;
    //printf("dis = %lld\n",dis);
}

ll pro(){
    iota(rep,rep+n,0);
    fill(sz,sz+n,1);
    fill(sds,sds+n,0);
    fill(ss,ss+n,0);
    fill(dep,dep+n,0);
    fill(vis,vis+n,0);
    S.clear();
    dis = 0;
    for(int i = 0; i < n; i++) G[i].clear(), C[i].clear();

    sort(P,P+n);
    int cur = 0;
    for(int i = 0; i < n; i++) S[ll(P[i].va) << 32 | P[i].vb] = i;
    for(int i = 1; i < n; i++){
        if(P[cur].va != P[i].va){
            cur = i;
            continue;
        }
        if(P[i].vb - P[i-1].vb == 1){
            c(i-1, i);
        }
    }
    for(int i = 0; i < n; i++){
        ll V = ll(P[i].va-1) << 32 | P[i].vb;
        if(S.count(V)){
            G[f(S[V])].push_back(f(i));
            G[f(i)].push_back(f(S[V]));
        }
    }
    /*
    for(int i = 0; i < n; i++){
        printf("(%d,%d) : %d\n",P[i].va,P[i].vb,f(i));
    }
    */
    for(int i = 0; i < n; i++){
        if(i != f(i)) continue;
        sort(all(G[i]));
        G[i].resize(unique(all(G[i])) - G[i].begin());
        //printf("%d, sz = %d: ",i,sz[i]); for(int u : G[i]) printf("%d ",u); puts("");
    }
    dfsi(f(0));
    dfs(f(0));
    return dis;
}

int DistanceSum(int N, int *X, int *Y){
    n = N;
    for(int i = 0; i < N; i++) P[i] = {X[i],Y[i]};
    ll d1 = pro();
    for(int i = 0; i < N; i++) P[i] = {Y[i],X[i]};
    ll d2 = pro();
    return (d1 + d2) % mod;
}
/*
int main(){
    fio;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> P[i].va >> P[i].vb;
    ll d1 = pro();
    for(int i = 0; i < n; i++) swap(P[i].va, P[i].vb);
    ll d2 = pro();
    cout << (d1 + d2) % mod << '\n';
}
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 7 ms 5072 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct
5 Correct 7 ms 5376 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 9 ms 5376 KB Output is correct
8 Correct 10 ms 5376 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 8 ms 5248 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 7552 KB Output is correct
2 Correct 23 ms 7672 KB Output is correct
3 Correct 52 ms 10892 KB Output is correct
4 Correct 59 ms 10920 KB Output is correct
5 Correct 107 ms 16876 KB Output is correct
6 Correct 97 ms 16904 KB Output is correct
7 Correct 111 ms 16876 KB Output is correct
8 Correct 95 ms 17004 KB Output is correct
9 Correct 101 ms 16620 KB Output is correct
10 Correct 112 ms 21436 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7952 KB Output is correct
2 Correct 35 ms 8028 KB Output is correct
3 Correct 77 ms 12044 KB Output is correct
4 Correct 69 ms 11916 KB Output is correct
5 Correct 166 ms 18996 KB Output is correct
6 Correct 190 ms 18440 KB Output is correct
7 Correct 156 ms 19308 KB Output is correct
8 Correct 149 ms 18500 KB Output is correct
9 Correct 120 ms 17964 KB Output is correct
10 Correct 128 ms 17964 KB Output is correct