# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1104668 | monaxia | Swap (BOI16_swap) | C++17 | 1 ms | 336 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define eps (long long)(1e-9)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const ll Mod = 1e9 + 7;
struct Node{
int x, y, z, index;
};
void solve(){
int n, start, end, ans = 0;
cin >> n >> start >> end;
vector <Node> a(n + 1);
vector <int> v_index(n + 1, 0), v_value(3 * n + 5), cpr, cnt(3 * n + 5, 0);
vector <vector <Node>> node(3 * n + 5);
queue <Node> q;
for(int i = 1; i <= n; i ++) {
cin >> a[i].x >> a[i].y >> a[i].z;
cpr.pb(a[i].x);
cpr.pb(a[i].y);
cpr.pb(a[i].z);
a[i].index = i;
}
sort(all(cpr));
for(int i = 1; i <= n; i ++) {
a[i].x = lower_bound(all(cpr), a[i].x) - cpr.begin() + 1;
a[i].y = lower_bound(all(cpr), a[i].y) - cpr.begin() + 1;
a[i].z = lower_bound(all(cpr), a[i].z) - cpr.begin() + 1;
map <int, int> appear;
if(appear.find(a[i].x) == appear.end()) node[a[i].x].pb(a[i]), appear[a[i].x] = 1;
if(appear.find(a[i].y) == appear.end()) node[a[i].y].pb(a[i]), appear[a[i].y] = 1;
if(appear.find(a[i].z) == appear.end()) node[a[i].z].pb(a[i]), appear[a[i].z] = 1;
}
q.push(a[start]);
v_index[start] = 1;
while(!q.empty()){
int x = q.front().x, y = q.front().y, z = q.front().z, index = q.front().index;
q.pop();
if(index == end){
cout << cnt[end];
return;
}
v_index[index] = 1;
if(!v_value[x]){
v_value[x] = 1;
for(auto& e : node[x]){
if(v_index[e.index]) continue;
v_index[e.index] = 1;
cnt[e.index] = cnt[index] + 1;
q.push(e);
}
}
if(!v_value[y]){
v_value[y] = 1;
for(auto& e : node[y]){
if(v_index[e.index]) continue;
v_index[e.index] = 1;
cnt[e.index] = cnt[index] + 1;
q.push(e);
}
}
if(!v_value[z]){
v_value[z] = 1;
for(auto& e : node[z]){
if(v_index[e.index]) continue;
v_index[e.index] = 1;
cnt[e.index] = cnt[index] + 1;
q.push(e);
}
}
}
cout << -1;
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
if(fopen("blank.inp", "r")){
freopen("blank.inp", "r", stdin);
freopen("blank.out", "w", stdout);
}
// cout << 1; return 0;
ll n = 1;
cin >> n;
while(n) {
solve();
n --;
cout << "\n";
}
// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |