Submission #155404

#TimeUsernameProblemLanguageResultExecution timeMemory
155404aer0parkIdeal city (IOI12_city)C++14
23 / 100
55 ms8432 KiB
#include <bits/stdc++.h> #define f first #define s second using namespace std; typedef int ll; typedef pair<ll,ll> pi; //간선 연결후 tree dp해보자 ll x[100005],y[100005],sz[100005],num[100005],cnt,anw,n; const long long mod=1e9; vector<ll> g[100005]; vector<pi> ar; ll dfs(ll a,ll p) { ll ret=sz[a]; for(int i=0;i<g[a].size();i++) if(g[a][i]!=p) ret+=dfs(g[a][i],a); anw=(anw+(long long)ret*(n-ret))%mod; return ret; } void add(ll a,ll b) { g[a].push_back(b),g[b].push_back(a); } void calc() { sort(ar.begin(),ar.end()); //점 0부터. for(int i=0;i<=n;i++) g[i].clear(),sz[i]=0; cnt=0; num[0]=++cnt,sz[cnt]=1; for(int i=1;i<ar.size();i++) { if(ar[i-1].s+1==ar[i].s) num[i]=cnt; else num[i]=++cnt; sz[cnt]++; } ll j=0,i=0; while(ar[j].f!=ar[0].f) j++; while(j<n) { while(j<n&&ar[i].f+1!=ar[j].f) { if(ar[i].f>=ar[j].f) j++; else i++; } while(j<n&&ar[i].f+1==ar[j].f&&ar[i].s!=ar[j].s) { if(ar[i].s>ar[j].s) j++; else i++; } ll ad=j; if(num[i]!=num[j]) add(num[i],num[j]),j++; while(num[j]==num[ad]) j++; } dfs(1,-1); } int DistanceSum (int N, int *X, int *Y) { ios::sync_with_stdio(false); cin.tie(NULL); n=N; for(int i=1;i<=n;i++) x[i]=X[i-1],y[i]=Y[i-1]; for(int i=1;i<=n;i++) ar.push_back({x[i],y[i]}); calc(); for(int i=0;i<n;i++) swap(ar[i].f,ar[i].s); calc(); return anw; }

Compilation message (stderr)

city.cpp: In function 'll dfs(ll, ll)':
city.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[a].size();i++)
              ~^~~~~~~~~~~~
city.cpp: In function 'void calc()':
city.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<ar.size();i++)
              ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...