제출 #114146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114146		Shtef	Grad (COI14_grad)	C++14	21 / 100	1568 ms	10168 KiB

grad

#include <iostream>
#include <utility>
#include <vector>
#include <cmath>
#include <cstring>
#include <queue>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef pair <int, double> pid;
typedef pair <ll, ll> pll;
typedef pair <double, int> pdi;
#define x first
#define y second
#define mp make_pair

vector <pll> a;
int n;
vector <pid> ms[100005];
double dist[100005];
bool bio[100005];
priority_queue <pdi, vector <pdi>, greater <pdi> > q;
const double inf = 1e100;

double udaljenost(int x, int y){
	return sqrt((a[x].x - a[y].x) * (a[x].x - a[y].x) + (a[x].y - a[y].y) * (a[x].y - a[y].y));
}

double kolko(int tx, int ty){
	memset(bio, 0, sizeof(bio));
	for(int i = 0 ; i < (int)a.size() ; ++i){
		dist[i] = inf;
	}
	dist[tx] = 0;
	q.push(mp(0, tx));
	while(!q.empty()){
		int x = q.top().y;
		q.pop();
		if(bio[x])
			continue;
		bio[x] = 1;
		for(vector <pid>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
			pid o = *i;
			if(dist[x] + o.y < dist[o.x]){
				dist[o.x] = dist[x] + o.y;
				q.push(mp(dist[o.x], o.x));
			}
		}
	}
	return dist[ty];
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tx, ty;
cin >> tx >> ty;
a.push_back(mp(tx, ty));
cin >> tx >> ty;
a.push_back(mp(tx, ty));
double t = udaljenost(0, 1);
ms[0].push_back(mp(1, t));
ms[1].push_back(mp(0, t));
cin >> n;
cout << fixed << setprecision(12);
for(int i = 0 ; i < n ; ++i){
	char type;
	cin >> type;
	if(type == 'd'){
		int x, y, prvi, drugi;
		cin >> x >> y >> prvi >> drugi;
		prvi--;
		drugi--;
		a.push_back(mp(x, y));
		t = udaljenost((int)a.size() - 1, prvi);
		ms[(int)a.size() - 1].push_back(mp(prvi, t));
		ms[prvi].push_back(mp((int)a.size() - 1, t));
		t = udaljenost((int)a.size() - 1, drugi);
		ms[(int)a.size() - 1].push_back(mp(drugi, t));
		ms[drugi].push_back(mp((int)a.size() - 1, t));
	}
	else{
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		/*
		for(int j = 0 ; j < (int)a.size() ; ++j){
			for(vector <pid>::iterator v = ms[j].begin() ; v != ms[j].end() ; ++v){
				pid o = *v;
				cout << "[" << o.x << "][" << o.y << "] ";
			}
			cout << endl;
		}
		*/
		cout << kolko(x, y) << endl;
	}
}

return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 6
• Subtask 6: 0 / 6
• Subtask 7: 0 / 6
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11
• Subtask 11: 0 / 11
• Subtask 12: 0 / 11