oj.uz

Submission #562601

# Submission time Handle Problem Language Result Execution time Memory
562601 2022-05-14T19:59:59 Z Leo121 Ideal city (IOI12_city) C++14
100 / 100
 430 ms 25736 KB 
#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int (a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int (a); i >= int(b); -- i)
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

const int maxn = 1e5;
const int mx[4] = {0, 0, 1, -1};
const int my[4] = {1, -1, 0, 0};
map<pii, int> mapa;
set<int> aux[maxn];
vi treex[maxn];
vi treey[maxn];
int szx[maxn];
int szy[maxn];
int compx[maxn];
int compy[maxn];
int arre[maxn][4];
bool visitadox[maxn];
bool visitadoy[maxn];
ll res;
int n;
ll mod = 1e9;
void dfsx(int u, int p){
    for(auto v : treex[u]){
        if(v != p){
            dfsx(v, u);
            res += ((ll) n - (ll) szx[v]) * (ll) szx[v];
            res %= mod;
            szx[u] += szx[v];
        }
    }
}
void dfsy(int u, int p){
    for(auto v : treey[u]){
        if(v != p){
            dfsy(v, u);
            res += ((ll) n - (ll) szy[v]) * (ll) szy[v];
            res %= mod;
            szy[u] += szy[v];
        }
    }
}
void moverme(int i, int compo, int ini){
    while(ini != -1){
        if(i <= 1){
            compy[ini] = compo;
            visitadoy[ini] = 1;
        }
        else{
            compx[ini] = compo;
            visitadox[ini] = 1;
        }
        ini = arre[ini][i];
    }
}
int DistanceSum(int N, int *X, int *Y) {
    n = N;
    forn(i, 0, N - 1){
        mapa[mp(X[i], Y[i])] = i;
    }
    memset(arre, -1, sizeof(arre));
    forn(i, 0, N - 1){
        forn(j, 0, 3){
            if(mapa.count(mp(X[i] + mx[j], Y[i] + my[j]))){
                arre[i][j] = mapa[mp(X[i] + mx[j], Y[i] + my[j])];
            }
        }
    }
    ///x
    int compox = -1, compoy = -1;
    forn(i, 0, N - 1){
        if(!visitadoy[i]){
            moverme(0, ++ compoy, i);
            moverme(1, compoy, i);
        }
        if(!visitadox[i]){
            moverme(2, ++ compox, i);
            moverme(3, compox, i);
        }
    }
    ///visitado y
    forn(i, 0, N - 1){
        forn(j, 2, 3){
            if(mapa.count(mp(X[i] + mx[j], Y[i] + my[j]))){
                aux[compy[i]].insert(compy[mapa[mp(X[i] + mx[j], Y[i] + my[j])]]);
            }
        }
    }
    forn(i, 0, compoy){
        for(auto j : aux[i]){
            treey[i].pb(j);
        }
        aux[i].clear();
    }
    forn(i, 0, N - 1){
        forn(j, 0, 1){
            if(mapa.count(mp(X[i] + mx[j], Y[i] + my[j]))){
                aux[compx[i]].insert(compx[mapa[mp(X[i] + mx[j], Y[i] + my[j])]]);
            }
        }
        szx[compx[i]] ++;
        szy[compy[i]] ++;
    }
    forn(i, 0, compox){
        for(auto j : aux[i]){
            treex[i].pb(j);
        }
        aux[i].clear();
    }
    dfsx(0, 0);
    dfsy(0, 0);
    return (int) res;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11440 KB Output is correct
2 Correct 8 ms 11376 KB Output is correct
3 Correct 10 ms 11512 KB Output is correct
4 Correct 11 ms 11384 KB Output is correct
5 Correct 10 ms 11476 KB Output is correct
6 Correct 9 ms 11520 KB Output is correct
7 Correct 9 ms 11576 KB Output is correct
8 Correct 10 ms 11476 KB Output is correct
9 Correct 10 ms 11420 KB Output is correct
10 Correct 9 ms 11476 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 12972 KB Output is correct
2 Correct 59 ms 13004 KB Output is correct
3 Correct 150 ms 15412 KB Output is correct
4 Correct 149 ms 15476 KB Output is correct
5 Correct 413 ms 19432 KB Output is correct
6 Correct 398 ms 19624 KB Output is correct
7 Correct 417 ms 19868 KB Output is correct
8 Correct 418 ms 19380 KB Output is correct
9 Correct 379 ms 20104 KB Output is correct
10 Correct 396 ms 24512 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13960 KB Output is correct
2 Correct 59 ms 13768 KB Output is correct
3 Correct 157 ms 18560 KB Output is correct
4 Correct 175 ms 17528 KB Output is correct
5 Correct 403 ms 25504 KB Output is correct
6 Correct 410 ms 22352 KB Output is correct
7 Correct 403 ms 25736 KB Output is correct
8 Correct 401 ms 22472 KB Output is correct
9 Correct 430 ms 21784 KB Output is correct
10 Correct 403 ms 21696 KB Output is correct