oj.uz

Submission #315589

# Submission time Handle Problem Language Result Execution time Memory
315589 2020-10-23T08:58:35 Z talant117408 Ideal city (IOI12_city) C++17
100 / 100
 70 ms 6380 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <ll, ll> pii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int mod = 1e9;
int n;

ll add(ll a, ll b){
    a = ((a%mod)+mod)%mod;
    b = ((b%mod)+mod)%mod;
    return (a+b)%mod;
}

ll mult(ll a, ll b){
    a = ((a%mod)+mod)%mod;
    b = ((b%mod)+mod)%mod;
    return (a*b)%mod;
}

struct point{
    int x, y;
    point(int _x, int _y){
        x = _x;
        y = _y;
    }
};

bool cmp(point& a, point& b){
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

vector <point> squs;

void revert(){
    for(int i = 0; i < n; i++){
        squs[i] = point(squs[i].y, squs[i].x);
    }
}

struct node{
    int x, ymin, ymax;
    vector <int> neighs;
    node(int _x, int _ymin, int _ymax){
        x = _x;
        ymin = _ymin;
        ymax = _ymax;
    }
};

vector <node> nodes;
ll total;
vector <bool> vis(100007);

void make_tree(){
    sort(all(squs), cmp);
    nodes.clear();
    
    int cnt = 0;
    while(cnt < n){
        int x = squs[cnt].x;
        int ymin = squs[cnt].y;
        int y = ymin;
        int i;
        
        for(i = cnt+1; i < n; i++){
            if(squs[i].y != y+1) break;
            y++;
        }
        
        int ymax = y;
        cnt = i;
        
        nodes.pb(node(x, ymin, ymax));
    }
    
    int cnt1 = 0, cnt2;
    
    for(cnt2 = 1; cnt2 < sz(nodes); cnt2++){
        while((nodes[cnt1].x+1 < nodes[cnt2].x) || (nodes[cnt1].x+1 == nodes[cnt2].x && nodes[cnt1].ymax < nodes[cnt2].ymin)){
            cnt1++;
        }
        int flag = 0;
        while(nodes[cnt1].x+1 == nodes[cnt2].x && nodes[cnt1].ymin <= nodes[cnt2].ymax){
            nodes[cnt1].neighs.pb(cnt2);
            nodes[cnt2].neighs.pb(cnt1);
            cnt1++;
            flag++;
        }
        if(flag) cnt1--;
    }
}

ll weight(int i){
    return nodes[i].ymax-nodes[i].ymin+1;
}

ll dfs(int u){
    if(vis[u]) return 0;
    vis[u] = 1;
    
    ll w = weight(u);
    for(int i = 0; i < sz(nodes[u].neighs); i++){
        w = add(w, dfs(nodes[u].neighs[i]));
    }
    
    total = add(total, mult(w, n-w));
    return w;
}

ll get(){
    make_tree();
    total = 0;
    for(int i = 0; i < sz(nodes); i++){
        vis[i] = 0;
    }
    
    dfs(0);
    
    return total;
}

int DistanceSum(int N, int *X, int *Y){
    
    n = N;
    for(int i = 0; i < n; i++){
        squs.pb(point(X[i], Y[i]));
    }
    pii sol; 
    sol.first = get();
    revert();
    sol.second = get();
    
    return add(sol.first, sol.second);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 896 KB Output is correct
2 Correct 10 ms 1056 KB Output is correct
3 Correct 24 ms 1792 KB Output is correct
4 Correct 25 ms 1792 KB Output is correct
5 Correct 49 ms 3068 KB Output is correct
6 Correct 50 ms 3060 KB Output is correct
7 Correct 51 ms 3192 KB Output is correct
8 Correct 49 ms 3060 KB Output is correct
9 Correct 50 ms 3068 KB Output is correct
10 Correct 55 ms 6380 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1308 KB Output is correct
2 Correct 12 ms 1372 KB Output is correct
3 Correct 33 ms 3120 KB Output is correct
4 Correct 29 ms 2556 KB Output is correct
5 Correct 69 ms 5996 KB Output is correct
6 Correct 56 ms 4208 KB Output is correct
7 Correct 70 ms 5996 KB Output is correct
8 Correct 59 ms 4208 KB Output is correct
9 Correct 55 ms 3952 KB Output is correct
10 Correct 53 ms 3824 KB Output is correct