oj.uz

Submission #698565

# Submission time Handle Problem Language Result Execution time Memory
698565 2023-02-13T20:00:44 Z arneves Ideal city (IOI12_city) C++17
100 / 100
 68 ms 11868 KB 
/*
	  ______  _____  _______ _     _ _______ __   _  _____  _  _  _
	 |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
	 |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
	
	
		   .      .           .      .           .      .    	
		   _\/  \/_           _\/  \/_           _\/  \/_    	
			_\/\/_             _\/\/_             _\/\/_     	
		_\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_ 	
		 / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \  	
			_/\/\_             _/\/\_             _/\/\_     	
			/\  /\             /\  /\             /\  /\     	
		   '      '           '      '           '      '    	
	
*/
 
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
 
 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>

using namespace std;

struct seg{
	int id,l,r;
};

void dfs(int s, int p, vector<vector<int> > &adj, vector<int> &d){
	
	for(auto u: adj[s]){
		if(u==p) continue;
		
		dfs(u,s,adj,d);
		
		d[s]+=d[u];
	}
}

long long solve(int N, int *X, int *Y){
	
	long long int ans=0;
	
	map<int, vector<int> >mapi;
	
	for(int i=0; i<N; i++){
		mapi[X[i]].push_back(Y[i]);
	}
	
	int c=0;
	
	map<int, vector<seg> > comp;
	
	for(auto &u: mapi){
		sort(u.second.begin(), u.second.end());
		
		int l=u.second[0],r=l;
		
		for(int i=1; i<u.second.size(); i++){
			if(u.second[i]==u.second[i-1]+1) r++;
			else{
				comp[u.first].push_back({c,l,r});
				l=r=u.second[i];
				c++;
			}
		}
		
		comp[u.first].push_back({c,l,r});
		c++;
	}
	
	vector<vector<int> > adj(c, vector<int>());
	
	for(const auto &u: comp){
		int y=u.first;
		
		if(comp[y+1].size()==0){
			comp.erase(y+1);
			continue;
		}
		
		vector<seg> v1=comp[y];
		vector<seg> v2=comp[y+1];
		
		int i=0, j=0;
		int n=v1.size(), m=v2.size();
		
		while(i<n && j<m) {
			int l=max(v1[i].l, v2[j].l);
			int r=min(v1[i].r, v2[j].r);
			
			if(l <= r){
				adj[v1[i].id].push_back(v2[j].id);
				adj[v2[j].id].push_back(v1[i].id);
			}
			
			if(v1[i].r<v2[j].r) i++;
			else j++;
		}
	}
	
	vector<int> subtreesize(c);
	
	for(const auto &u: comp){
		for(const seg i: u.second){
			subtreesize[i.id]=i.r-i.l+1;
		}
	}
	
	dfs(0, -1, adj, subtreesize);
	
	for(int i=0; i<c; i++){
		for(int j: adj[i]){
			if(j>i){
				long long k=min(subtreesize[i], subtreesize[j]);
				ans+=k*(((long long) N)-k);
				ans%=1'000'000'000;
			}
		}
	}
	
	return ans;
}

int DistanceSum(int N, int *X, int *Y) {
	
	long long ans=0;
	
	ans+=solve(N,X,Y);
	ans+=solve(N,Y,X);
	
	ans%=1000'000'000;
	
	return ans;
}

Compilation message

city.cpp: In function 'long long int solve(int, int*, int*)':
city.cpp:86:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i=1; i<u.second.size(); i++){
      |                ~^~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 724 KB Output is correct
2 Correct 7 ms 760 KB Output is correct
3 Correct 18 ms 1172 KB Output is correct
4 Correct 17 ms 1364 KB Output is correct
5 Correct 37 ms 1980 KB Output is correct
6 Correct 42 ms 2836 KB Output is correct
7 Correct 39 ms 3068 KB Output is correct
8 Correct 45 ms 2564 KB Output is correct
9 Correct 38 ms 3236 KB Output is correct
10 Correct 68 ms 11868 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1304 KB Output is correct
2 Correct 11 ms 1132 KB Output is correct
3 Correct 26 ms 2704 KB Output is correct
4 Correct 24 ms 2116 KB Output is correct
5 Correct 56 ms 5096 KB Output is correct
6 Correct 46 ms 3980 KB Output is correct
7 Correct 55 ms 5796 KB Output is correct
8 Correct 49 ms 3932 KB Output is correct
9 Correct 41 ms 3524 KB Output is correct
10 Correct 41 ms 3388 KB Output is correct