oj.uz

답안 #383199

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
383199 2021-03-29T07:44:15 Z kshitij_sodani 이상적인 도시 (IOI12_city) C++14
100 / 100
 343 ms 21724 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

set<int> adj[100001];
const llo mod=1e9;
llo ans=0;
llo ss[100001];

llo tt[100001];
llo nn;
void dfs(int no,int par=-1){
	ss[no]=tt[no];
	for(auto j:adj[no]){
		if(j!=par){
			//cout<<no<<":"<<j<<endl;
			dfs(j,no);
			ans+=(nn-ss[j])*ss[j];
			ans%=mod;
			ss[no]+=ss[j];
		}
	}
}
void solve(vector<int> x ,vector<int> y){
	int n=x.size();
	nn=n;
	//cout<<11<<endl;
	vector<pair<int,int>> ss;
	for(int i=0;i<n;i++){
		ss.pb({x[i],y[i]});
	}
	sort(ss.begin(),ss.end());
	int ind=0;
	int cot=-1;
	map<pair<int,int>,int> yy;
	for(int i=0;i<n;i++){
		adj[i].clear();
		tt[i]=0;
	}
	while(ind<ss.size()){
		cot++;
		pair<int,int> cur=ss[ind];
		while(ind<ss.size()){
			if(ss[ind].a!=cur.a){
				break;
			}
			if(ss[ind].b==cur.b){
				tt[cot]++;
				yy[ss[ind]]=cot;
				cur.b+=1;
				ind+=1;
			}
			else{
				break;
			}
		}
	}

	for(int i=0;i<n;i++){
		vector<int> zz={1,-1};
		vector<int> zz2={0,0};
		for(int j=0;j<2;j++){
			pair<int,int> ne={ss[i].a+zz[j],ss[i].b+zz2[j]};
			if(yy.find(ne)!=yy.end()){
				adj[yy[ss[i]]].insert(yy[ne]);
				adj[yy[ne]].insert(yy[ss[i]]);
			}
		}
	}
	dfs(0);
	

}
int DistanceSum(int n, int *xx, int *yy) {

	

	//sort(xx.begin(),ss.end());
	vector<int> x;
	vector<int> y;
	for(int i=0;i<n;i++){
		x.pb(xx[i]);
		y.pb(yy[i]);
	}
	solve(x,y);
	solve(y,x);



 	return (int)ans;

}

Compilation message

city.cpp: In function 'void solve(std::vector<int>, std::vector<int>)':
city.cpp:46:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  while(ind<ss.size()){
      |        ~~~^~~~~~~~~~
city.cpp:49:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   while(ind<ss.size()){
      |         ~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 5 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 5 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 5 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 5 ms 5100 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5228 KB Output is correct
2 Correct 6 ms 5228 KB Output is correct
3 Correct 8 ms 5228 KB Output is correct
4 Correct 8 ms 5356 KB Output is correct
5 Correct 9 ms 5356 KB Output is correct
6 Correct 11 ms 5356 KB Output is correct
7 Correct 8 ms 5356 KB Output is correct
8 Correct 9 ms 5356 KB Output is correct
9 Correct 9 ms 5228 KB Output is correct
10 Correct 9 ms 5228 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 7496 KB Output is correct
2 Correct 63 ms 7496 KB Output is correct
3 Correct 162 ms 10780 KB Output is correct
4 Correct 163 ms 10780 KB Output is correct
5 Correct 335 ms 16552 KB Output is correct
6 Correct 331 ms 16468 KB Output is correct
7 Correct 329 ms 16824 KB Output is correct
8 Correct 331 ms 16312 KB Output is correct
9 Correct 343 ms 16604 KB Output is correct
10 Correct 301 ms 21724 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 8264 KB Output is correct
2 Correct 62 ms 8136 KB Output is correct
3 Correct 143 ms 12696 KB Output is correct
4 Correct 160 ms 12060 KB Output is correct
5 Correct 294 ms 20452 KB Output is correct
6 Correct 342 ms 18088 KB Output is correct
7 Correct 294 ms 20792 KB Output is correct
8 Correct 341 ms 18232 KB Output is correct
9 Correct 318 ms 17584 KB Output is correct
10 Correct 321 ms 17592 KB Output is correct