SCPC Week 10 Solutions

Late to SCPC

Original Problem

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1000000;
vector<int> adj[N];
int dis[N];
bool vis[N];
 
void bfs(int x) {
    vis[x] = true;
    dis[x] = 0;
    queue<int> q;
    q.push(x);
    while (!q.empty()) {
        int s = q.front(); q.pop();
 
        for (auto u : adj[s]) {
            if (vis[u]) 
                continue;
            vis[u] = true;
            dis[u] = dis[s] + 1;
            q.push(u);
        }
    }
}
 
void solve() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
 
    for (int i = 0; i < n; i++) {
        vis[i] = false;
        dis[i] = -1;
    }
 
    int u, v;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        adj[u - 1].push_back(v - 1);
        adj[v - 1].push_back(u - 1);
    }
 
    bfs(s - 1);
    cout << dis[t - 1] << endl;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
}

Love Triangle

Original Problem Link: https://codeforces.com/contest/939/problem/A

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
typedef long long ll;
 
void solve() {
    int n; cin >> n;
 
    int num;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> num;
        nums[i] = num - 1;
    }
 
    for (int i = 0; i < n; i++) {
        if (nums[nums[nums[i]]] == i) {
            cout << "YES" << endl;
            return;
        }
    }
 
    cout << "NO" << endl;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
}

Party

Original Problem Link: https://codeforces.com/contest/115/problem/A

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
typedef long long ll;
 
const int N = 10000;
vector<int> adj[N];
int vis[N];
int max_dis = 0;
 
void dfs(int s, int dis) {
    if (vis[s]) return;
    vis[s] = true;
 
    max_dis = max(max_dis, dis);
    for (auto u: adj[s])
        dfs(u, dis + 1);
}
 
void solve() {
    int n; cin >> n;
 
    int num;
    vector<int> roots;
    for (int i = 0; i < n; i++) {
        cin >> num;
 
        if (num != -1)
            adj[num - 1].push_back(i);
        else
            roots.push_back(i);
    }
 
    for (int node : roots)
        dfs(node, 1);
 
    cout << max_dis << endl;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
}

Ice Skating

Original Problem Link: https://codeforces.com/contest/217/problem/A

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
typedef long long ll;
 
const int N = 10000;
vector<int> adj[N];
int vis[N];
int max_dis = 0;
 
void dfs(int s) {
    if (vis[s]) return;
    vis[s] = true;
 
    for (auto u: adj[s])
        dfs(u);
}
 
void solve() {
    int n; cin >> n;
 
    vector<int> xs(n);
    vector<int> ys(n);
    for (int i = 0; i < n; i++) {
        cin >> xs[i] >> ys[i];
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (xs[i] == xs[j] or ys[i] == ys[j]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
 
    int comps = 0;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            comps += 1;
            dfs(i);
        }
    }
    cout << comps - 1 << endl;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
}

Enshadowed

Original Problem (Adapted from NZOI Training Site)

Tutorial: https://kiwirafe.github.io/en/nzic2023-round3-tutorial-3/

Solution:

#include <bits/stdc++.h>
using namespace std;

#define euclid(x1, x2, y1, y2) sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2))

// Dijkstra's Algorithm
// Be cautious to use double since the problem can have decimals.
double dijkstra(int source, int target, vector<pair<int, double>> *adj, int n) {
    double distance[n];
    bool processed[n];
    for(int i = 0; i < n; i++){
        distance[i] = INT_MAX;
        processed[i] = false;
    }

    priority_queue<pair<double, int>> q;
    distance[source] = 0;
    q.push({0, source});
    while(!q.empty()) {
        int a = q.top().second; q.pop();
        if(processed[a]) continue;
        processed[a] = true;
        for(auto u : adj[a]) {
            int b = u.first; double w = u.second;
            if (distance[a] + w < distance[b]) {
                distance[b] = distance[a] + w;
                q.push({-distance[b], b});
            }
        }
    }

    return distance[target];
}

int main() {
    double x1, y1, r1, x2, y2, r2, xq, yq, rq;
    int N;

    cin >> x1 >> y1 >> x2 >> y2;
    cin >> N;

    vector<tuple<double, double, double>> circles;
    for (int i = 0; i < N; i++) {
        cin >> xq >> yq >> rq;
        circles.push_back({xq, yq, rq});
    }

    // Add the the starting and ending nodes.
    circles.push_back({x1, y1, 0});
    circles.push_back({x2, y2, 0});

    // Calculate the distance between the nodes.
    vector<pair<int, double>> adj[N + 2];
    for (int i = 0; i < N + 2; i++) {
        for (int j = 0; j < N + 2; j++) {
            tie(x1, y1, r1) = circles[i];
            tie(x2, y2, r2) = circles[j];
            // Euclid is defined earlier.
            adj[i].push_back({j, max(euclid(x1, x2, y1, y2) - r1 - r2, 0.0)});
        }
    }

    double distance = dijkstra(N, N + 1, adj, N + 2);

    // Return 6dp due to problem requirement.
    printf("%.6f\n", distance);
    
}