oj.uz

Submission #592726

# Submission time Handle Problem Language Result Execution time Memory
592726 2022-07-09T14:03:12 Z Blagojce City Mapping (NOI18_citymapping) C++11
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define pb push_back
#define pq priority_queue
#define all(x) begin(x), end(x)
 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
 
const int mxn = 1003;
mt19937 _rand(time(NULL));
clock_t z;
 
#include "citymapping.h"
 
ll dist[mxn][mxn];/*
ll get_distance(int x, int y){
	cout<<"? "<<x<<' '<<y<<endl;
	ll ret;
	cin >> ret;
	return ret;
}*/
ll ask(int x, int y){
	if(x != y && dist[x][y] == 0){
		dist[x][y] = dist[y][x] = get_distance(x+1, y+1);
	}
	return dist[x][y];
}
vector<int> g;
int R1, R2;
 
 
int AA[mxn], BB[mxn], WW[mxn];
int edge_id = 0;
 
void add_edge(int x, int y, int w){
	AA[edge_id] = x;
	BB[edge_id] = y;
	WW[edge_id] = w;
	edge_id ++;
}
 
 
 
 
void decompose(vector<int> v){
	
	
	if((int)g.size() <= 1) return;
	
	int r1 = v[1 + (_rand() % ((int)v.size()-1))];
	g = v;
	
	for(auto u : g){
		ask(u, r1);
	}
	
	R1 = r1;
	sort(all(g), [](const int &i, const int &j){
		return dist[R1][i] < dist[R1][j];
	});
	int r2 = v[0];
	
	for(auto u : g){
		ask(u, r2);
	}
	
	
	
	vector<int> diam;
	for(auto u : g){
		if(dist[r1][u] + dist[u][r2] == dist[r1][r2]){
			diam.pb(u);
		}
	}
	
	fr(i, 1, (int)diam.size()){
		add_edge(diam[i-1], diam[i], dist[r1][diam[i]] - dist[r1][diam[i-1]]);
	}
	vector<int> sub[(int)diam.size()];
	fr(i, 0, (int)diam.size()){
		sub[i].pb(diam[i]);
	}
	
	for(auto u : g){
		if(dist[r1][u] + dist[u][r2] == dist[r1][r2]) continue;
		fr(i, 0, (int)diam.size()){
			auto d = diam[i];
			if(dist[r1][u] - dist[r2][u] == dist[r1][d] - dist[r2][d]){
				sub[i].pb(u);
				break;
			}
		}
	}
	
	fr(i, 0, (int)diam.size()){
		int d = diam[i];
		for(auto s : sub[i]){
			dist[d][s] = dist[s][d] = dist[r1][s] - dist[r1][d];
		}
	}
	
	
	fr(i, 0, (int)diam.size()){
		decompose(sub[i]);
	}
}
 
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	vector<int> v;
	fr(i, 0, N) v.pb(i);
	decompose(v);
	fr(i, 0, N-1){
		A[i] = AA[i] + 1;
		B[i] = BB[i] + 1;
		W[i] = WW[i];
	}
	return;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -