Submission #366448

#TimeUsernameProblemLanguageResultExecution timeMemory
366448CodePlatinaMagenta (COCI21_magenta)C++14
30 / 110
86 ms7404 KiB
#include <iostream> #include <vector> #include <algorithm> #include <utility> #define pii pair<int, int> #define piii pair<int, pii> #define pll pair<long long, long long> #define plll pair<long long, pll> #define ff first #define ss second #define ee ss.ff #define rr ss.ss //#define DEBUG using namespace std; vector<pii> gph[101010]; pii par[101010]; int dst(int x, int p, int y, int d) { if(x == y) return d; for(auto [i, j] : gph[x]) if(i != p) { int t = dst(i, x, y, d + 1); if(t != -1) return t; } return -1; } void dfs(int x, int p) { vector<pii> tmp; for(auto [y, i] : gph[x]) if(y != p) { tmp.push_back({y, i}); par[y] = {x, i}; dfs(y, x); } gph[x] = tmp; } bool sol(int x, int s) { if(s == 1) { for(auto [y, i] : gph[x]) if(i) return true; return false; } for(auto [y, i] : gph[x]) { if(i == 1) if(sol(y, 1)) return true; if(i == 2) if(sol(y, 0)) return true; } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; int a, b; cin >> a >> b; --a; --b; for(int i = 1; i < n; ++i) { int x, y; cin >> x >> y; --x; --y; int c; #ifdef DEBUG cin >> c; #else //DEBUG string st; cin >> st; if(st == "plava") c = 0; else if(st == "crvena") c = 1; else c = 2; #endif //DEBUG gph[x].push_back({y, c}); gph[y].push_back({x, c}); } bool flag = false; for(auto i : gph[a]) if(i.ss != 1 && i.ff != b) flag = true; if(!flag) { cout << "Marin"; return 0; } flag = false; for(auto i : gph[b]) if(i.ss != 0) flag = true; if(!flag) { cout << "Paula"; return 0; } int d = dst(a, -1, b, 0); int x = a, y = b; if(d & 1) { swap(x, y); for(int i = 0; i < n; ++i) for(auto &j : gph[i]) if(j.ss < 2) j.ss = 1 - j.ss; } dfs(x, -1); int root = y; for(int i = 0; i < (d - 1) / 2; ++i) { if(!par[root].ss) break; root = par[root].ff; } for(int i = root; i != x; i = par[i].ff) if(par[i].ss == 1) { cout << "Magneta"; return 0; } if(sol(root, 0)) cout << "Magneta"; else if(d & 1) cout << "Marin"; else cout << "Paula"; }

Compilation message (stderr)

Main.cpp: In function 'int dst(int, int, int, int)':
Main.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto [i, j] : gph[x]) if(i != p)
      |              ^
Main.cpp: In function 'void dfs(int, int)':
Main.cpp:34:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for(auto [y, i] : gph[x]) if(y != p)
      |              ^
Main.cpp: In function 'bool sol(int, int)':
Main.cpp:47:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |         for(auto [y, i] : gph[x]) if(i) return true;
      |                  ^
Main.cpp:51:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for(auto [y, i] : gph[x])
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...