oj.uz

Submission #1021946

# Submission time Handle Problem Language Result Execution time Memory
1021946 2024-07-13T08:04:21 Z vjudge1 Ideal city (IOI12_city) C++17
100 / 100
 222 ms 25008 KB 
#include<bits/stdc++.h>
using namespace std;
struct union_find{
    int par[100100],sz[100100];
    void RS(){memset(par,0,sizeof par);for(auto&i:sz)i=1;}
    union_find(){RS();}
    int comp(int x){
        return par[x]?par[x]=comp(par[x]):x;
    }
    void merge(int a,int b){
        a=comp(a); b=comp(b);
        if(a<b) swap(a,b);
        if(a-b) par[a]=b,
            sz[b]+=sz[a];
    }
} UF;
int mod=1e9;
long long ANS;
vector<int>adj[100100];
set<int>adj2[100100];
map<pair<int,int>,int>S;
long long SZ[100100];
void dfs(int n,int p,int x){
    for(auto i:adj2[n])
        if(i-p)dfs(i,n,x),
            SZ[n]+=SZ[i];
    ANS+=SZ[n]*(x-SZ[n]);
}
int DistanceSum(int N, int *X, int *Y) {
    int A=*min_element(Y,Y+N);
    int B=*min_element(X,X+N);
    for(int i=0;i<N;i++)
        S[{X[i]-=B,Y[i]-=A}]=i+1;
    for(int i=N;i;i--)
        X[i]=X[i-1],Y[i]=Y[i-1];
    for(int i=1;i<=N;i++){
        if(S.count({X[i]-1,Y[i]}))
            adj[i].push_back(S[{X[i]-1,Y[i]}]);
        if(S.count({X[i]+1,Y[i]}))
            adj[i].push_back(S[{X[i]+1,Y[i]}]);
        if(S.count({X[i],Y[i]-1}))
            adj[i].push_back(S[{X[i],Y[i]-1}]);
        if(S.count({X[i],Y[i]+1}))
            adj[i].push_back(S[{X[i],Y[i]+1}]);
    }
    for(int i=1;i<=N;i++)
        for(auto x:adj[i])
            if(X[x]==X[i])
                UF.merge(x,i);
    for(int i=1;i<=N;i++)
        for(auto x:adj[i]) if(Y[x]==Y[i])
            adj2[UF.comp(x)].insert(UF.comp(i));
    for(int i=1;i<=N;i++)
        SZ[i]=UF.sz[i];
    dfs(1,0,N);
    UF.RS();
    for(int i=1;i<=N;i++)
        adj2[i].clear(),swap(X[i],Y[i]);
    for(int i=1;i<=N;i++)
        for(auto x:adj[i])
            if(X[x]==X[i])
                UF.merge(x,i);
    for(int i=1;i<=N;i++)
        for(auto x:adj[i]) if(Y[x]==Y[i])
            adj2[UF.comp(x)].insert(UF.comp(i));
    for(int i=1;i<=N;i++)
        SZ[i]=UF.sz[i];
    dfs(1,0,N);
    return ANS%mod;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 5 ms 8376 KB Output is correct
3 Correct 5 ms 8280 KB Output is correct
4 Correct 5 ms 8284 KB Output is correct
5 Correct 5 ms 8540 KB Output is correct
6 Correct 6 ms 8540 KB Output is correct
7 Correct 6 ms 8540 KB Output is correct
8 Correct 6 ms 8552 KB Output is correct
9 Correct 9 ms 8324 KB Output is correct
10 Correct 6 ms 8540 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10584 KB Output is correct
2 Correct 33 ms 10588 KB Output is correct
3 Correct 89 ms 14164 KB Output is correct
4 Correct 94 ms 14160 KB Output is correct
5 Correct 222 ms 20120 KB Output is correct
6 Correct 192 ms 20112 KB Output is correct
7 Correct 191 ms 20304 KB Output is correct
8 Correct 192 ms 20048 KB Output is correct
9 Correct 195 ms 20412 KB Output is correct
10 Correct 166 ms 25008 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 11348 KB Output is correct
2 Correct 36 ms 11084 KB Output is correct
3 Correct 99 ms 15952 KB Output is correct
4 Correct 90 ms 15288 KB Output is correct
5 Correct 203 ms 23632 KB Output is correct
6 Correct 191 ms 21596 KB Output is correct
7 Correct 209 ms 23912 KB Output is correct
8 Correct 195 ms 21704 KB Output is correct
9 Correct 214 ms 21328 KB Output is correct
10 Correct 197 ms 21072 KB Output is correct