Submission #315590

#	Time	Username	Problem	Language	Result	Execution time	Memory
315590		talant117408	Ideal city (IOI12_city)	C++17	23 / 100	53 ms	5604 KiB

city

#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++;
        }
        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++;
        }
    }
}

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: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 23 / 23
• Subtask 4: 0 / 45