제출 #333628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333628		keta_tsimakuridze	이상적인 도시 (IOI12_city)	C++14	32 / 100	192 ms	26348 KiB

city

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45