제출 #63715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63715		bazsi700	Adriatic (CEOI13_adriatic)	C++14	25 / 100	2115 ms	257256 KiB

adriatic

#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();
		}
	}
	if(n > 100)
	return 0;
	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 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20