結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 oshamashama
|
| 提出日時 | 2022-07-30 17:59:19 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,000 bytes |
| コンパイル時間 | 2,550 ms |
| 実行使用メモリ | 6,952 KB |
| スコア | 7,447,733 |
| 最終ジャッジ日時 | 2022-07-30 18:00:18 |
| 合計ジャッジ時間 | 33,541 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge10 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 29 WA * 1 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
const long long alpha = 5;
typedef long long ll;
struct solve
{
ll N, M;
ll best_score;
vector<pair<ll, ll>> planet_coordinate;
vector<pair<ll, ll>> station_coordinate;
vector<pair<ll, ll>> best_planet_coordinate;
vector<pair<ll, ll>> best_station_coordinate;
vector<vector<ll>> m;
vector<ll> d;
vector<ll> last;
solve()
{
cin >> N >> M;
best_score = 0;
best_planet_coordinate.resize(N);
best_station_coordinate.resize(M);
planet_coordinate.resize(N);
station_coordinate.resize(M);
m.resize(N + M, vector<ll>(N + M));
d.resize(N + M, 1e18);
last.resize(N + M, 1e18);
for (int i = 0; i < N; i++)
{
cin >> planet_coordinate.at(i).first >> planet_coordinate.at(i).second;
}
}
ll dist(pair<ll, ll> a, pair<ll, ll> b)
{
return ((a.first - b.first) * (a.first - b.first) +
(a.second - b.second) * (a.second - b.second));
}
ll distance(int i, int j)
{
return dist((i < N ? planet_coordinate.at(i) : station_coordinate.at(i - N)),
(j < N ? planet_coordinate.at(j) : station_coordinate.at(j - N))) *
(i < N ? 5 : 1) *
(j < N ? 5 : 1);
}
ll get_shortest(int &start, vector<bool> &used, queue<int> &q)
{
for (int i = 0; i < N + M; i++)
{
for (int j = 0; j < N + M; j++)
{
m.at(i).at(j) = distance(i, j);
}
}
priority_queue<pair<ll, ll>> pq;
d.resize(N + M, 1e18);
pq.push(make_pair(0, start));
ll Md = 1e18;
int ind = 0;
for (int i = 0; i < N + M; i++)
{
// cerr << "hoge" << d.at(i) << endl;
d.at(i) = 1e18;
}
d.at(start) = 0;
while (pq.size())
{
int now = pq.top().second;
pq.pop();
for (int i = 0; i < N + M; i++)
{
int next = i;
// cerr << "-----" << now << ' ' << next << endl;
// cerr << d.size() << endl;
// cerr << m.at(0).size() << endl;
// cerr << d.at(next) << endl;
if (d.at(next) > d.at(now) + m.at(now).at(next))
{
d.at(next) = d.at(now) + m.at(now).at(next);
last.at(next) = now;
// cout << "Md " << endl;
if (N <= next)
{
pq.push(make_pair(d.at(next), next));
}
else if (Md > d.at(next) &&
used.at(next) == false)
{
// cout << "/* code */" << endl;
Md = d.at(next);
ind = next;
}
}
}
}
// cout << ind << endl;
int next = ind;
if (ind != -1)
{
stack<int> s;
while (ind != start)
{
s.push(ind);
// cerr << "check " << ind << ' ' << last.at(ind) << endl;
ind = last.at(ind);
}
while (s.size())
{
q.push(s.top());
s.pop();
}
}
start = next;
used.at(start) = true;
return d.at(start);
}
void print_ans()
{
std::random_device rd;
std::default_random_engine eng(rd());
std::uniform_int_distribution<int> distr(200, 800);
std::uniform_int_distribution<int> distr2(-40, 40);
ll ccc = 10;
queue<int> best_q;
ll time_limit = 900000;
// while (clock() < time_limit / 2)
// {
// for (int i = 0; i < M; i++)
// {
// station_coordinate.at(i) = make_pair(distr(eng), distr(eng));
// // cerr << station_coordinate.at(i).first << ' ' << station_coordinate.at(i).second << endl;
// }
// queue<int> q;
// q.push(0);
// vector<bool> used(N + M, 0);
// used.at(0) = true;
// int start = 0;
// ll sum = 0;
// for (int i = 0; i < N; i++)
// {
// sum += get_shortest(start, used, q);
// // cout << start << endl;
// }
// ll now_score = 1000000000 / (1000 + sqrt(sum));
// if (now_score > best_score)
// {
// best_q = q;
// best_planet_coordinate = planet_coordinate;
// best_station_coordinate = station_coordinate;
// best_score = now_score;
// }
// }
station_coordinate.at(0) = make_pair(300, 300);
station_coordinate.at(1) = make_pair(700, 300);
station_coordinate.at(2) = make_pair(300, 700);
station_coordinate.at(3) = make_pair(700, 700);
station_coordinate.at(4) = make_pair(300, 500);
station_coordinate.at(5) = make_pair(500, 300);
station_coordinate.at(6) = make_pair(700, 500);
station_coordinate.at(7) = make_pair(500, 700);
while (clock() < time_limit)
{
for (int i = 0; i < M; i++)
{
station_coordinate.at(i) = make_pair(station_coordinate.at(i).first + distr2(eng),
station_coordinate.at(i).second + distr2(eng));
// cerr << station_coordinate.at(i).first << ' ' << station_coordinate.at(i).second << endl;
}
queue<int> q;
q.push(0);
vector<bool> used(N + M, 0);
used.at(0) = true;
int start = 0;
ll sum = 0;
for (int i = 0; i < N; i++)
{
sum += get_shortest(start, used, q);
// cout << start << endl;
}
ll now_score = 1000000000 / (1000 + sqrt(sum));
if (now_score > best_score)
{
best_q = q;
best_planet_coordinate = planet_coordinate;
best_station_coordinate = station_coordinate;
best_score = now_score;
}
}
cerr << best_score << endl;
for (int i = 0; i < M; i++)
{
cout << best_station_coordinate.at(i).first << ' ' << best_station_coordinate.at(i).second << endl;
}
cout << best_q.size() << endl;
while (best_q.size())
{
int now = best_q.front();
// cout << now << endl;
cout << 1 + now / N
<< ' '
<< now % N + 1
<< endl;
best_q.pop();
}
}
};
int main()
{
solve s;
s.print_ans();
return 0;
}