oj.uz

Submission #416364

# Submission time Handle Problem Language Result Execution time Memory
416364 2021-06-02T10:37:54 Z Emin2004 Ideal city (IOI12_city) C++14
100 / 100
 430 ms 16528 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define F first
#define S second

const int N = 100005;
const int mod = 1000000000;

vector<int> a[N];
int w[N], sub[N], used[N];
ll m;
set <pii> s;

void DFS(int node){
    used[node] = 1;
    sub[node] = w[node];
    for(int i : a[node]){
        if(!used[i]){
            DFS(i);
            sub[node] += sub[i];
        }
    }
}

ll getans(int node){
    ll res = sub[node] * (m - sub[node]) % mod;
    used[node] = 2;
    for(int i : a[node]){
        if(used[i] != 2){
            res += getans(i);
            res %= mod;
        }
    }
    return res;
}

int DistanceSum(int n, int *x, int *y) {
    for(int i = 0; i < n; i++){
        s.insert({x[i], y[i]});
    }
    map<pii, int> mp;
    int idx = (*s.begin()).F;
    int idy = (*s.begin()).S;
    int sz = 1, nn = 1;
    s.erase(s.begin());
    mp[{idx, idy}] = nn;
    while(s.size() > 0){
        int curx = (*s.begin()).F;
        int cury = (*s.begin()).S;
        s.erase(s.begin());
        if(curx == idx){
            if(cury == idy + sz) {
                sz++;
                mp[{curx, cury}] = nn;
            }
            else{
                idy = cury;
                w[nn] = sz;
                sz = 1;
                nn++;
                mp[{curx, cury}] = nn;
            }
        }
        else{
            w[nn] = sz;
            sz = 1;
            nn++;
            idy = cury;
            idx = curx;
            mp[{curx, cury}] = nn;
        }
    }
    w[nn] = sz;
    for(auto i : mp){
        int curx = i.F.F;
        int cury = i.F.S;
        int u = mp[{curx, cury}];
        if(mp[{curx - 1, cury}]){
            int v = mp[{curx - 1, cury}];
            if(mp[{curx - 1, cury}] == mp[{curx - 1, cury - 1}] && mp[{curx, cury}] == mp[{curx, cury - 1}]) continue;
            a[u].pb(v);
            a[v].pb(u);
        }
    }
    DFS(1);
    m = sub[1];
    ll ans = getans(1) % mod;

    for(int i = 1; i <= nn; i++){
        a[i].clear();
        used[i] = 0;
        sub[i] = 0;
        w[i] = 0;
    }
    mp.clear();
    for(int i = 0; i < n; i++){
        s.insert({y[i], x[i]});
    }
    idx = (*s.begin()).F;
    idy = (*s.begin()).S;
    sz = 1, nn = 1;
    s.erase(s.begin());
    mp[{idx, idy}] = nn;
    while(s.size() > 0){
        int curx = (*s.begin()).F;
        int cury = (*s.begin()).S;
        s.erase(s.begin());
        if(curx == idx){
            if(cury == idy + sz) {
                sz++;
                mp[{curx, cury}] = nn;
            }
            else{
                idy = cury;
                w[nn] = sz;
                sz = 1;
                nn++;
                mp[{curx, cury}] = nn;
            }
        }
        else{
            w[nn] = sz;
            sz = 1;
            nn++;
            idy = cury;
            idx = curx;
            mp[{curx, cury}] = nn;
        }
    }
    w[nn] = sz;
    for(auto i : mp){
        int curx = i.F.F;
        int cury = i.F.S;
        int u = mp[{curx, cury}];
        if(mp[{curx - 1, cury}]){
            int v = mp[{curx - 1, cury}];
            if(mp[{curx - 1, cury}] == mp[{curx - 1, cury - 1}] && mp[{curx, cury}] == mp[{curx, cury - 1}]) continue;
            a[u].pb(v);
            a[v].pb(u);
        }
    }
    DFS(1);
    m = sub[1];
    ll rtrn = ans + getans(1);
    rtrn %= mod;
    return rtrn;
}
/*
11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6
*/

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2764 KB Output is correct
2 Correct 6 ms 2780 KB Output is correct
3 Correct 5 ms 2764 KB Output is correct
4 Correct 7 ms 2788 KB Output is correct
5 Correct 9 ms 2892 KB Output is correct
6 Correct 9 ms 2884 KB Output is correct
7 Correct 7 ms 2920 KB Output is correct
8 Correct 8 ms 2880 KB Output is correct
9 Correct 7 ms 2816 KB Output is correct
10 Correct 6 ms 2764 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 4496 KB Output is correct
2 Correct 86 ms 4452 KB Output is correct
3 Correct 158 ms 7148 KB Output is correct
4 Correct 172 ms 7288 KB Output is correct
5 Correct 403 ms 11516 KB Output is correct
6 Correct 322 ms 11652 KB Output is correct
7 Correct 354 ms 11828 KB Output is correct
8 Correct 364 ms 11444 KB Output is correct
9 Correct 338 ms 11788 KB Output is correct
10 Correct 356 ms 16320 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5332 KB Output is correct
2 Correct 59 ms 5076 KB Output is correct
3 Correct 179 ms 9528 KB Output is correct
4 Correct 158 ms 8576 KB Output is correct
5 Correct 387 ms 16296 KB Output is correct
6 Correct 408 ms 13512 KB Output is correct
7 Correct 397 ms 16528 KB Output is correct
8 Correct 307 ms 13632 KB Output is correct
9 Correct 430 ms 12960 KB Output is correct
10 Correct 356 ms 12836 KB Output is correct