oj.uz

Submission #588377

# Submission time Handle Problem Language Result Execution time Memory
588377 2022-07-03T08:42:06 Z MilosMilutinovic Magenta (COCI21_magenta) C++14
30 / 110
 121 ms 16240 KB 
/**
 *    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);
  vector<vector<int>> cnt(n, vector<int>(4));
  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);
    cnt[u][t] += 1;
    cnt[v][t] += 1;
  }
  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 (w == 3 && cnt[u][2] + cnt[u][3] > 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 (w == 1 && cnt[u][1] + cnt[u][2] > 1) {
          ok = true;
        }          
        Dfs(u, v);
      }
    };
    Dfs(a, a);
    cout << (ok ? "Magenta" : "Marin") << '\n';
  }
  return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 16180 KB Output is correct
2 Correct 121 ms 16216 KB Output is correct
3 Correct 80 ms 16224 KB Output is correct
4 Correct 78 ms 16240 KB Output is correct
5 Correct 82 ms 16232 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -