제출 #1178179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178179		THXuan	Magenta (COCI21_magenta)	C++20	30 / 110	32 ms	14152 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <array>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#define INF 1e9
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll MAXN = 100005;

int d[MAXN], p[MAXN][20];
vector<int>adj[MAXN];

void dfs(int s, int e) {
    for (int i = 1; i <= 18; i++) {
        p[s][i] = p[p[s][i - 1]][i - 1];
    }
    for (auto u : adj[s]) {
        if (u == e) continue;
        d[u] = d[s] + 1;
        p[u][0] = s;
        dfs(u, s);
    }
}

int lca(int a, int b) {
    if (d[a] > d[b])swap(a, b);
    int dis = d[b] - d[a];
    for (int i = 0; i <= 18; i++) {
        if (dis & (1 << i)) b = p[b][i];
    }
    if (a == b) return a;
    for (int i = 18; i >= 0; i--) {
        if (p[a][i] != p[b][i]) {
            a = p[a][i];
            b = p[b][i];
        }
    }
    return p[a][0];
}

void solve() {
    int n; cin >> n;
    int a, b; cin >> a >> b;
    for (int i = 1; i <= n - 1; i++) {
        int u, v; string s; cin >> u >> v>>s;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    int x = lca(a, b);
    int dist = (d[a] - d[x]) + (d[b] - d[x]);
    if (dist % 2 == 0)cout << "Paula" << "\n";
    else cout << "Marin" << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;// cin>>t;
    while (t--) solve();
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50