Submission #588390

#	Time	Username	Problem	Language	Result	Execution time	Memory
588390		MilosMilutinovic	Magenta (COCI21_magenta)	C++14	110 / 110	81 ms	10160 KiB

Main

/**
 *    author:  wxhtzdy
 *    created: 02.07.2022 21:03:17
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n;
  int a, b;
  cin >> a >> b;
  --a; --b;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    string foo;
    cin >> foo;
    --u; --v;
    int t;
    if (foo == "plava") {
      t = 1;
    } else if (foo == "magenta") {
      t = 2;      
    } else {
      t = 3;
    }
    g[u].emplace_back(v, t);
    g[v].emplace_back(u, t);
  }
  vector<int> dep(n);
  vector<int> par(n);
  function<void(int, int)> Dfs = [&](int v, int pr) {
    par[v] = pr;
    dep[v] = dep[pr] + 1;
    for (auto& e : g[v]) {
      int u = e.first;
      if (u == pr) {
        continue;
      }
      Dfs(u, v);
    }
  };
  Dfs(0, 0);
  int x = a, y = b, dis = 0;
  while (x != y) {
    if (dep[x] > dep[y]) {
      x = par[x];
    } else {
      y = par[y];
    }
    dis += 1;
  }            
  vector<vector<int>> dist(2, vector<int>(n, -1));
  {                                            
    dist[0][a] = 0;
    vector<int> que(1, a);
    for (int x = 0; x < (int) que.size(); x++) {
      int i = que[x];
      for (auto& e : g[i]) {
        int u = e.first;
        int w = e.second;
        if (w <= 2 && dist[0][u] == -1) {
          dist[0][u] = dist[0][i] + 1;
          que.push_back(u);            
        }
      }
    }
  }
  {                                            
    dist[1][b] = 0;
    vector<int> que(1, b);
    for (int x = 0; x < (int) que.size(); x++) {
      int i = que[x];
      for (auto& e : g[i]) {
        int u = e.first;
        int w = e.second;
        if (w >= 2 && dist[1][u] == -1) {
          dist[1][u] = dist[1][i] + 1;
          que.push_back(u);            
        }
      }
    }
  }
  bool have = false;
  for (auto& e : g[a]) {
    if (e.first != b && e.second <= 2) {
      have = true;
    }
  }
  if (!have) {
    cout << "Marin" << '\n';
    return 0;
  }
  if (dis % 2 == 0) {
    if (dist[0][b] == -1 && (int) g[b].size() > 1) {
      cout << "Magenta" << '\n';
      return 0;
    }
    bool ok = false;
    function<void(int, int)> Dfs = [&](int v, int pr) {
      for (auto& e : g[v]) {
        int u = e.first;
        int w = e.second;
        if (u == pr || w == 1 || (dist[0][u] != -1 && dist[0][u] <= dist[1][u])) {
          continue;
        }
        if (dist[0][v] == -1 && dist[0][u] == -1) {
          ok = true;
        }          
        Dfs(u, v);
      }
    };
    Dfs(b, b);
    cout << (ok ? "Magenta" : "Paula") << '\n';
  } else { 
    have = false;
    for (auto& e : g[b]) {
      if (e.second >= 2) {
        have = true;
      }
    }
    if (!have) {
      cout << "Paula" << '\n';
      return 0;
    }
    have = false;
    for (auto& e : g[a]) {
      if (e.second <= 2 && dist[1][e.first] == -1) {
        have = true;
      }
    }
    if (dist[1][a] == -1 && have) {
      cout << "Magenta" << '\n';
      return 0;
    }
    bool ok = false;
    function<void(int, int)> Dfs = [&](int v, int pr) {
      for (auto& e : g[v]) {
        int u = e.first;
        int w = e.second;
        if (u == pr || w == 3 || (dist[1][u] != -1 && dist[1][u] < dist[0][u])) {
          continue;
        }   
        if (dist[1][v] == -1 && dist[1][u] == -1) {
          ok = true;
        }
        Dfs(u, v);
      }
    };
    Dfs(a, a);
    cout << (ok ? "Magenta" : "Marin") << '\n';
  }
  return 0;
}

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