Submission #416353

#	Time	Username	Problem	Language	Result	Execution time	Memory
416353		Emin2004	Ideal city (IOI12_city)	C++14	32 / 100	51 ms	5316 KiB

city

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

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]);
    used[node] = 2;
    for(int i : a[node]){
        if(used[i] != 2){
            res += getans(i);
        }
    }
    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);

    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];
    return ans + getans(1);
}
/*
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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45