Submission #39544

#TimeUsernameProblemLanguageResultExecution timeMemory
39544smu201111192Ideal city (IOI12_city)C++14
55 / 100
1000 ms20488 KiB
#include <iostream> #include <cstdio> #include <fstream> #include <cassert> #include <string> #include <sstream> #include <algorithm> #include <set> #include <numeric> #include <cmath> #include <map> #include <vector> #include <queue> #include <stack> #include <cstring> #include <queue> #include <numeric> #include <iomanip> #define ll long long using namespace std; const int MAXN = 100005; map<pair<int,int>,int> mp; const int dy[4]={0,0,1,-1}; const int dx[4]={1,-1,0,0}; vector<int> adj[MAXN]; const int mod = 1000000000; long long dp[MAXN]; long long ts[MAXN]; long long parent[MAXN],sz[MAXN]; int vis[MAXN]; void init(){ memset(vis,0,sizeof(vis)); for(int i=0;i<MAXN;i++) adj[i].clear(); for(int i=0;i<MAXN;i++) parent[i] = i,sz[i] = 1 , dp[i] = 0; } int find(int u){ return u == parent[u] ? u : parent[u] = find(parent[u]); } void mrg(int u,int v){ u = find(u), v = find(v); if(u == v)return; parent[u] = v; sz[v] += sz[u]; } void dfs(int here){ vis[here] = 1; ts[here] = sz[find(here)]; for(int i=0;i<adj[here].size();i++){ int there = adj[here][i]; if(vis[there]) continue; dfs(there); ts[here] += ts[there]; } } void dfs2(int here,long long &ret,long long N){ vis[here] = 1; ret %= mod; for(int i=0;i<adj[here].size();i++){ int there = adj[here][i]; if(vis[there]) continue; ret += ts[there] * (N-ts[there]); dfs2(there,ret,N); } } void addEdge(int u,int v){ adj[find(u)].push_back(find(v)); adj[find(v)].push_back(find(u)); } int DistanceSum(int N, int *X, int *Y) { mp.clear(); for(int i=0;i<N;i++){ swap(X[i],Y[i]); } for(int i=0;i<N;i++){ mp[make_pair(Y[i],X[i])] = -1; } int id = 0; for(auto it = mp.begin(); it!= mp.end(); it++){ it->second = ++id; } init(); for(int i=0;i<N;i++){ pair<int,int> cur = make_pair(Y[i],X[i]); pair<int,int> bef = make_pair(Y[i]-1,X[i]); pair<int,int> nxt = make_pair(Y[i]+1,X[i]); if(mp.find(bef) != mp.end()) mrg(mp[bef],mp[cur]); if(mp.find(nxt) != mp.end()) mrg(mp[nxt],mp[cur]); } for(int i=0;i<N;i++){ pair<int,int> cur = make_pair(Y[i],X[i]); pair<int,int> bef = make_pair(Y[i],X[i]-1); pair<int,int> nxt = make_pair(Y[i],X[i]+1); if(mp.find(bef) != mp.end()) addEdge(mp[bef],mp[cur]); if(mp.find(nxt) != mp.end()) addEdge(mp[nxt],mp[cur]); } long long ret = 0; dfs(find(1)); memset(vis,0,sizeof(vis)); dfs2(find(1),ret,N); init(); for(int i=0;i<N;i++){ pair<int,int> cur = make_pair(Y[i],X[i]); pair<int,int> bef = make_pair(Y[i],X[i]-1); pair<int,int> nxt = make_pair(Y[i],X[i]+1); if(mp.find(bef) != mp.end()) mrg(mp[bef],mp[cur]); if(mp.find(nxt) != mp.end()) mrg(mp[nxt],mp[cur]); } for(int i=0;i<N;i++){ pair<int,int> cur = make_pair(Y[i],X[i]); pair<int,int> bef = make_pair(Y[i]-1,X[i]); pair<int,int> nxt = make_pair(Y[i]+1,X[i]); if(mp.find(bef) != mp.end()) addEdge(mp[bef],mp[cur]); if(mp.find(nxt) != mp.end()) addEdge(mp[nxt],mp[cur]); } dfs(find(1)); memset(vis,0,sizeof(vis)); dfs2(find(1),ret,N); return (int)ret; }

Compilation message (stderr)

city.cpp: In function 'void dfs(int)':
city.cpp:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[here].size();i++){
                  ^
city.cpp: In function 'void dfs2(int, long long int&, long long int)':
city.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[here].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...