oj.uz

답안 #63713

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63713 2018-08-02T14:15:22 Z bazsi700 섬 항해 (CEOI13_adriatic) C++14
25 / 100
 2000 ms 252740 KB 
#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vii graph(n,vi());
	vector<pair<pair<int,int>,int> > cord (n);
	vector<int> r(n);
	vector<int> c(n);
	for(int i = 0; i < n; i++) {
		cin >> r[i] >> c[i];
		cord[i] = {{r[i],c[i]},i};
	}
	sort(cord.begin(),cord.end());
	set<pair<int,int> > was;
	vi toins;
	for(int i = 0; i < n; i++) {
		toins.push_back(cord[i].second);
		for(auto el : was) {
			if(el.first >= cord[i].first.second) {
				break;
			}
			graph[cord[i].second].push_back(el.second);
			graph[el.second].push_back(cord[i].second);
		}
		if(i != n-1 && cord[i+1].first.first > cord[i].first.first) {
			for(int el : toins) {
				was.insert({c[el],el});
			}
			toins.clear();
		}
	}
	for(int i = 0; i < n; i++) {
		vector<int> dist (n,-1);
		queue<int> q;
		dist[i] = 0;
		q.push(i);
		ll sum = 0;
		while(!q.empty()) {
			int v = q.front();
			q.pop();
			sum+= dist[v];
			for(int u : graph[v]) {
				if(dist[u] == -1) {
					dist[u] = dist[v]+1;
					q.push(u);
				}
			}
		}
		cout << sum << "\n";
	}
	return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 444 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 4 ms 552 KB Output is correct
5 Correct 2 ms 552 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 1384 KB Output is correct
2 Execution timed out 2041 ms 7372 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2013 ms 7372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2066 ms 252740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2082 ms 252740 KB Time limit exceeded
2 Halted 0 ms 0 KB -