oj.uz

Submission #868399

# Submission time Handle Problem Language Result Execution time Memory
868399 2023-10-31T11:31:16 Z abcvuitunggio Ideal city (IOI12_city) C++17
100 / 100
 265 ms 15868 KB 
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9;
int p[100000],sz[100000],n,res,vis[100000];
vector <int> ke[100000];
int f(int i){
    return (p[i]==i?i:p[i]=f(p[i]));
}
void unite(int i, int j){
    i=f(i);
    j=f(j);
    if (i==j)
        return;
    if (sz[i]<sz[j])
        swap(i,j);
    sz[i]+=sz[j];
    p[j]=i;
}
void dfs(int u, int p){
    vis[u]=1;
    for (int v:ke[u])
        if (!vis[v]&&v!=p){
            dfs(v,u);
            sz[u]+=sz[v];
        }
    res=(res+1LL*sz[u]*(n-sz[u])%mod)%mod;
}
int calc(int *x, int *y){
    map <pair <int, int>, int> mp;
    for (int i=0;i<n;i++){
        mp[{x[i],y[i]}]=i;
        p[i]=i;
        sz[i]=1;
        vis[i]=0;
        ke[i].clear();
    }
    for (int i=0;i<n;i++)
        if (mp.count({x[i]-1,y[i]}))
            unite(mp[{x[i]-1,y[i]}],i);
    for (int i=0;i<n;i++)
        if (mp.count({x[i],y[i]-1})){
            int j=f(mp[{x[i],y[i]-1}]);
            ke[f(i)].push_back(j);
            ke[j].push_back(f(i));
        }
    res=0;
    dfs(f(0),-1);
    return res;
}
int DistanceSum(int N, int *X, int *Y){
    n=N;
    return (calc(X,Y)+calc(Y,X))%mod;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 2 ms 2804 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 3 ms 3012 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 3 ms 3008 KB Output is correct
8 Correct 3 ms 2896 KB Output is correct
9 Correct 3 ms 2908 KB Output is correct
10 Correct 3 ms 2908 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4944 KB Output is correct
2 Correct 34 ms 5156 KB Output is correct
3 Correct 97 ms 8424 KB Output is correct
4 Correct 95 ms 8392 KB Output is correct
5 Correct 221 ms 14328 KB Output is correct
6 Correct 211 ms 14316 KB Output is correct
7 Correct 234 ms 14284 KB Output is correct
8 Correct 218 ms 14548 KB Output is correct
9 Correct 212 ms 13916 KB Output is correct
10 Correct 224 ms 15868 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4944 KB Output is correct
2 Correct 33 ms 5204 KB Output is correct
3 Correct 92 ms 8380 KB Output is correct
4 Correct 99 ms 8680 KB Output is correct
5 Correct 206 ms 14100 KB Output is correct
6 Correct 215 ms 14284 KB Output is correct
7 Correct 265 ms 14164 KB Output is correct
8 Correct 231 ms 14368 KB Output is correct
9 Correct 234 ms 14180 KB Output is correct
10 Correct 216 ms 14300 KB Output is correct