oj.uz

Submission #274841

# Submission time Handle Problem Language Result Execution time Memory
274841 2020-08-19T16:41:28 Z shayan_p Ideal city (IOI12_city) C++14
100 / 100
 531 ms 14824 KB 
// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10;
const int Nine = (int)1e9;

vector<int> v[maxn];

int pr[maxn];

int fnd(int u){
    return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
bool mrg(int a, int b){
    if( (a = fnd(a)) == (b = fnd(b)) )
	return 0;
    if(pr[a] > pr[b])
	swap(a, b);
    pr[a]+= pr[b];
    pr[b] = a;
    return 1;
}
int SZ[maxn];
int dfs(int tot, int u, int par = -1){
    int ans = 0;
    SZ[u] = -pr[fnd(u)];
    for(int y : v[u]){
	if(y != par){
	    ans = (ans + dfs(tot, y, u)) % Nine;
	    SZ[u]+= SZ[y];
	}
    }
    ans = (1ll * ans + 1ll * SZ[u] * (tot - SZ[u])) % Nine;
    return ans;
}
void add_edge(int a, int b){
    v[a].PB(b);
    v[b].PB(a);
}
int solve(int n, int *X, int *Y){
    for(int i = 0; i < n; i++){
	v[i].clear();
    }
    
    memset(pr, -1, sizeof pr);
    
    map<pii, int> mp;
    for(int i = 0; i < n; i++)
	mp[{X[i], Y[i]}] = i;
    vector<int> vc;    
    for(int i = 0; i < n; i++){
	if(mp.count({X[i], Y[i]+1}))
	    mrg(i, mp[{X[i], Y[i]+1}]);	
    }
    for(int i = 0; i < n; i++){
	if(mp.count({X[i]+1, Y[i]}))
	    vc.PB(i);
    }
    sort(vc.begin(), vc.end(), [&](int i, int j){ return Y[i] < Y[j]; });
    for(int a : vc){
	int b = mp[{X[a]+1, Y[a]}];
	if(mp.count({X[a], Y[a]+1}) == 0 || mp.count({X[a]+1, Y[a]+1}) == 0)
	    add_edge(fnd(a), fnd(b));
    }
    return dfs(n, fnd(0));
}
int ITER = 0;
int DistanceSum(int n, int *X, int *Y){
    assert(++ITER <= 1);
    return (solve(n, X, Y) + solve(n, Y, X)) % Nine;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5040 KB Output is correct
2 Correct 62 ms 4992 KB Output is correct
3 Correct 179 ms 7608 KB Output is correct
4 Correct 169 ms 7732 KB Output is correct
5 Correct 442 ms 11748 KB Output is correct
6 Correct 483 ms 11964 KB Output is correct
7 Correct 511 ms 12164 KB Output is correct
8 Correct 515 ms 11748 KB Output is correct
9 Correct 531 ms 12132 KB Output is correct
10 Correct 451 ms 14824 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 5276 KB Output is correct
2 Correct 56 ms 5112 KB Output is correct
3 Correct 159 ms 8444 KB Output is correct
4 Correct 165 ms 8160 KB Output is correct
5 Correct 430 ms 13700 KB Output is correct
6 Correct 441 ms 12980 KB Output is correct
7 Correct 429 ms 13824 KB Output is correct
8 Correct 426 ms 12844 KB Output is correct
9 Correct 455 ms 12692 KB Output is correct
10 Correct 442 ms 12560 KB Output is correct