Submission #156934

#	Time	Username	Problem	Language	Result	Execution time	Memory
156934		brcode	City Mapping (NOI18_citymapping)	C++14	32 / 100	32 ms	1276 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
map<pair<int,int>,long long> m1;
int weight[1005];
vector<pair<int,int>> v3[1005];
vector< pair<long long, int> > v1;
vector<int> blocked;
bool block[1005];
vector<int> tour;
long long getdist(int x,int y) {
	if (x==y) return 0;
	if (x > y) swap(x,y);
	if (!m1[make_pair(x,y)]){
		return m1[make_pair(x,y)] = get_distance(x+1, y+1);
	}
	else return m1[make_pair(x, y)];
}



int dfs(int x, int p) {
	int ans = 1;
	tour.push_back(x);
	for (int i = 0; i < v3[x].size(); i++){
	    if (!block[v3[x][i].first]){
	         ans += dfs(v3[x][i].first,x);
	    }
	} 
	return weight[x] = ans;
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	int root = 0;
	for (int i = 0; i < N; i++) {
		if (i!=root) v1.push_back(make_pair(getdist(root, i), i));
	}
	sort(v1.begin(), v1.end());
	
	for (int i = 0; i < v1.size(); i++) {
		int currnode = v1[i].second;
		long long dist = v1[i].first;
		int currroot = root;
		while (1) {
			vector< pair<int, long long> > v2;
			long long curd = 0;
			tour.clear();
			dfs(currroot, -1);
			if (weight[currroot] == 1) {
				A[i] = currnode + 1;
				B[i] = currroot + 1;
				W[i] = getdist(root, currnode) - getdist(root, currroot);
				v3[currroot].push_back(make_pair(currnode, W[i]));
				for (int j = 0; j < blocked.size(); j++) block[blocked[j]] = 0;
				blocked.clear();
				break;
			}
			
			int mnd = 1000000000, node = -1;
			for (int j = 0; j < tour.size(); j++) {
				if (max(weight[tour[j]], weight[currroot] - weight[tour[j]]) < mnd) {
					mnd = max(weight[tour[j]], weight[currroot] - weight[tour[j]]);
					node = tour[j];
				}
			}
			
			long long d = getdist(currnode, node);
			if (d + getdist(root, node) == getdist(root, currnode)) {
				currroot = node;
			} else {
			    if(currroot != root){
			        for(auto x:v3[currroot]){
			            if(x.first != node){
			                currroot = x.first;
			            }
			        }
			    }
				block[node] = 1;
				blocked.push_back(node);
			}
		}
	}
}

Compilation message (stderr)

citymapping.cpp: In function 'int dfs(int, int)':
citymapping.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v3[x].size(); i++){
                  ~~^~~~~~~~~~~~~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v1.size(); i++) {
                  ~~^~~~~~~~~~~
citymapping.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < blocked.size(); j++) block[blocked[j]] = 0;
                     ~~^~~~~~~~~~~~~~~~
citymapping.cpp:60:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < tour.size(); j++) {
                    ~~^~~~~~~~~~~~~
citymapping.cpp:46:14: warning: unused variable 'curd' [-Wunused-variable]
    long long curd = 0;
              ^~~~
citymapping.cpp:42:13: warning: unused variable 'dist' [-Wunused-variable]
   long long dist = v1[i].first;
             ^~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 0 / 43