oj.uz

Submission #144633

# Submission time Handle Problem Language Result Execution time Memory
144633 2019-08-17T09:57:55 Z gs18115 Ideal city (IOI12_city) C++14
100 / 100
 106 ms 16184 KB 
#include<vector>
#include<algorithm>
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const ll inf=1e18;
const ll mod=1e9;
vector<int>adj[100010];
ll ans;
int sz[100010];
int s2[100010];
ll dp[100010];
void dfs(int x,int p)
{
    sz[x]=s2[x];
    for(int t:adj[x])
    {
        if(t==p)
            continue;
        dfs(t,x);
        sz[x]+=sz[t];
    }
    dp[x]=sz[x];
    for(int t:adj[x])
        if(t!=p)
            ans=(ans+dp[t]*(sz[x]-sz[t]))%mod,dp[x]+=dp[t];
    return;
}
inline void solv(vector<pl>&p)
{
    int n=p.size();
    int i;
    int cnt=0;
    vector<int>ind;
    ind.eb(cnt);
    sort(all(p));
    for(i=1;i<n;i++)
    {
        if(p[i].fi==p[i-1].fi&&p[i].se==p[i-1].se+1)
            ind.eb(cnt);
        else
            ind.eb(++cnt);
    }
    cnt++;
    for(i=0;i<cnt;i++)
        s2[i]=0;
    for(i=0;i<cnt;i++)
        adj[i].clear();
    for(i=0;i<n;i++)
        s2[ind[i]]++;
    vector<pair<pl,int> >P;
    for(i=0;i<n;i++)
        P.eb(pl(p[i].se,p[i].fi),ind[i]);
    sort(all(P));
    for(i=1;i<n;i++)
    {
        pl&t=P[i].fi;
        pl&s=P[i-1].fi;
        if(t.fi==s.fi&&t.se==s.se+1)
        {
            adj[P[i].se].eb(P[i-1].se);
            adj[P[i-1].se].eb(P[i].se);
        }
    }
    for(i=0;i<=cnt;i++)
    {
        sort(all(adj[i]));
        adj[i].erase(unique(all(adj[i])),adj[i].end());
    }
    dfs(0,-1);
    return;
}
int DistanceSum(int N,int*X,int*Y)
{
    vector<pl>P;
    int i;
    for(i=0;i<N;i++)
        P.eb(X[i],Y[i]);
    solv(P);
    P.clear();
    for(i=0;i<N;i++)
        P.eb(Y[i],X[i]);
    solv(P);
    return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5012 KB Output is correct
2 Correct 21 ms 5016 KB Output is correct
3 Correct 47 ms 7932 KB Output is correct
4 Correct 46 ms 7924 KB Output is correct
5 Correct 92 ms 13368 KB Output is correct
6 Correct 93 ms 13204 KB Output is correct
7 Correct 92 ms 13344 KB Output is correct
8 Correct 92 ms 12984 KB Output is correct
9 Correct 91 ms 12988 KB Output is correct
10 Correct 89 ms 16184 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5136 KB Output is correct
2 Correct 22 ms 5140 KB Output is correct
3 Correct 54 ms 8276 KB Output is correct
4 Correct 52 ms 8148 KB Output is correct
5 Correct 106 ms 13892 KB Output is correct
6 Correct 101 ms 13352 KB Output is correct
7 Correct 105 ms 14160 KB Output is correct
8 Correct 100 ms 13376 KB Output is correct
9 Correct 106 ms 13400 KB Output is correct
10 Correct 98 ms 13244 KB Output is correct