oj.uz

Submission #114146

# Submission time Handle Problem Language Result Execution time Memory
114146 2019-05-30T15:55:33 Z Shtef Grad (COI14_grad) C++14
21 / 100
 1500 ms 10168 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2816 KB 41 numbers

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2816 KB 300 numbers

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2944 KB 500 numbers

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1551 ms 6436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1531 ms 7832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1546 ms 10168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1546 ms 7668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1563 ms 10096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1568 ms 4964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1560 ms 6000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1560 ms 4756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1555 ms 4748 KB Time limit exceeded
2 Halted 0 ms 0 KB -