Submission #39512

#TimeUsernameProblemLanguageResultExecution timeMemory
39512smu201111192Ideal city (IOI12_city)C++14
0 / 100
69 ms3732 KiB
#include <iostream> #include <cstdio> #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; 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[4005]; const int mod = 1000000000; int dist[4005]; void addEdge(int u,int v){ adj[u].push_back(v); adj[v].push_back(u); } int bfs(int here){ memset(dist,-1,sizeof(dist)); dist[here] = 0; queue<int> q; q.push(here); while(!q.empty()){ int here = q.front(); q.pop(); for(int i=0;i<adj[here].size();i++){ int there = adj[here][i]; if(dist[there] == -1){ dist[there] = dist[here] + 1; q.push(there); } } } int ret = 0; for(int i = 0;i<4000;i++){ if(i > here){ ret += dist[i]; ret %= mod; } } return ret; } int DistanceSum(int N, int *X, int *Y) { for(int i=0;i<N;i++){ mp[make_pair(Y[i],X[i])]; } int id = 0; for(auto it = mp.begin();it!=mp.end();it++){ it->second = ++id; } for(int i=0;i<N;i++){ int x = X[i]; int y = Y[i]; for(int k=0;k<4;k++){ int ny = y + dy[k]; int nx = x + dx[k]; if(mp.find(make_pair(ny,nx)) != mp.end()){ addEdge(mp[make_pair(y,x)],mp[make_pair(ny,nx)]); } } } int tot = 0; for(int i=0;i<N;i++){ tot += bfs(i); tot %= mod; } return tot; }

Compilation message (stderr)

city.cpp: In function 'int bfs(int)':
city.cpp:36:22: 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...