oj.uz

답안 #333628

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
333628 2020-12-07T09:18:36 Z keta_tsimakuridze 이상적인 도시 (IOI12_city) C++14
32 / 100
 192 ms 26348 KB 
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=1e5+5;
const int mod=1e9;
int s[N],ans,n,cnt,X[N],Y[N];
pair<int,int>a[N];
map<pair<int,int>,int>mp;
vector<int>V[N],v[N];
void dfs(int u,int p){
	s[u]=v[u].back()-v[u][0]+1;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]!=p){ 
			dfs(V[u][i],u);
			s[u]+=s[V[u][i]];
		}
	}
	ans+=s[u]*(n-s[u])%mod;//cout<<u<<" -- "<<s[u]<<endl;
	ans%=mod;
}
void Tree(){
	//cout<<"+"<<endl;
	 for(int i=0;i<n;i++){
  	if(!i || a[i].f!=a[i-1].f || a[i].s!=a[i-1].s+1){
  		cnt++;  
  	    //cout<<a[i].f<<" "<<a[i].s<<"_"<<cnt<<endl;
  	
	  }	mp[{a[i].f,a[i].s}]=cnt;v[cnt].push_back(a[i].s);
  }
  for(int i=0;i<n;i++){
  	if(mp[{a[i].f+1,a[i].s}]){
  		int cc=mp[{a[i].f+1,a[i].s}]; 
  		if(V[mp[{a[i].f,a[i].s}]].size()==0 || V[mp[{a[i].f,a[i].s}]].back()!=cc){
  		V[mp[{a[i].f,a[i].s}]].push_back(cc);
		V[cc].push_back(mp[{a[i].f,a[i].s}]);	
		}
	  }
  }
  dfs(1,0);
}
int DistanceSum(int N, int *X, int *Y) {
  for(int i=0;i<N;i++){
  	a[i]={X[i],Y[i]};
  } n=N;
  sort(a,a+N);
  Tree();
  for(int i=1;i<=cnt;i++)
    v[i].clear(),V[i].clear();
	cnt=0;
  for(int i=0;i<N;i++)
  mp[{a[i].f,a[i].s}]=0,swap(a[i].f,a[i].s); 
  sort(a,a+N);
  Tree();
  return ans;
}

Compilation message

city.cpp: In function 'void dfs(int, int)':
city.cpp:13:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 4 ms 5100 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 4 ms 5120 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct

Subtask #2
21.0 / 21.0

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

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 7532 KB Output is correct
2 Correct 32 ms 8428 KB Output is correct
3 Correct 75 ms 10860 KB Output is correct
4 Correct 84 ms 13164 KB Output is correct
5 Incorrect 141 ms 14956 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 9452 KB Output is correct
2 Correct 38 ms 9068 KB Output is correct
3 Correct 99 ms 15852 KB Output is correct
4 Correct 88 ms 14444 KB Output is correct
5 Incorrect 192 ms 26348 KB Output isn't correct
6 Halted 0 ms 0 KB -