Submission #987728

#TimeUsernameProblemLanguageResultExecution timeMemory
987728emad234Ideal city (IOI12_city)C++17
100 / 100
175 ms26792 KiB
#pragma once #include "bits/stdc++.h" #define F first #define S second #define ll long long #define pii pair<ll,ll> const int mxN = 2e5 + 5; const int mod = 1e9; using namespace std; vector<vector<int>>v; ll dpD[mxN],dpU[mxN]; ll subD[mxN],subU[mxN]; ll w[mxN]; int p[mxN]; ll ans; ll n; void dfs(int u,int par){ subD[u] = w[u]; p[u] = par; for(auto x : v[u]){ if(x == par) continue; dfs(x,u); subD[u] += subD[x]; } dpD[u] = (n - subD[u]) * subD[u]; } ll solve(int N,int X[],int Y[]){ ans = 0; for(int i = 0; i <= N;i++){ dpD[i] = 0; dpU[i] = 0; subD[i] = 0; subU[i] = 0; w[i] = 0; p[i] = 0; } map<pii,int>mp; map<pii,bool>vis; for(auto &x : v) x.clear(); v.clear(); v.resize(N + 1); int id = 0; vector<pii>a; for(int i = 0;i < N;i++){ a.push_back({X[i],Y[i]}); } sort(a.begin(),a.end()); int pX = -1,pY = -1; for(auto x : a){ if(x.F != pX || x.S != pY + 1){ id++; } mp[x] = id; w[id]++; if(mp[{x.F - 1,x.S}] && !vis[{mp[x],mp[{x.F - 1,x.S}]}]){ v[mp[{x.F - 1,x.S}]].push_back(mp[x]); v[mp[x]].push_back(mp[{x.F - 1,x.S}]); vis[{mp[x],mp[{x.F - 1,x.S}]}] = 1; } pX = x.F; pY = x.S; } // for(int i = 1;i < 7;i++){ // cout<<i<<' '<<w[i]<<"{ "; // for(auto x : v[i]){ // cout<<x<<' '; // } // cout<<"}\n"; // } dfs(1,0); for(int i = 1;i <= N;i++){ ans += dpD[i]; // cout<<dpD[i]<<' '; } // cout<<'\n'; // for(int i = 1;i <= N;i++){ // cout<<dpU[i]<<' '; // } // cout<<'\n'; // cout<<'\n'; // ans /= 2; // ans %= mod; return ans; } int DistanceSum(int N, int X[], int Y[]){ n = N; return (((solve(N,Y,X) + solve(N,X,Y))) % mod); }

Compilation message (stderr)

city.cpp:1:10: warning: #pragma once in main file
    1 |  #pragma once
      |          ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...