Submission #382875

#TimeUsernameProblemLanguageResultExecution timeMemory
382875ne4eHbKaMagenta (COCI21_magenta)C++17
30 / 110
83 ms8992 KiB
#include <bits/stdc++.h> using namespace std; #ifndef _LOCAL //#pragma GCC optimize("O3,Ofast") #else #pragma GCC optimize("O0") #endif template<typename t> inline void umin(t &a, const t b) {a = min(a, b);} template<typename t> inline void umax(t &a, const t b) {a = max(a, b);} typedef pair<int, int> pii; typedef long long ll; typedef long double ld; typedef int8_t byte; ll time() {return chrono::system_clock().now().time_since_epoch().count();} mt19937 rnd(time()); #define ft first #define sd second #define len(f) int((f).size()) #define bnd(f) (f).begin(), (f).end() #define _ <<' '<< const int inf = 1e9 + 5; const ll inf64 = 4e18 + 5; const int md = 998244353; namespace MD { void add(int &a, const int b) {if((a += b) >= md) a -= md;} void sub(int &a, const int b) {if((a -= b) < 0) a += md;} int prod(const int a, const int b) {return ll(a) * b % md;} }; const int N = 1e5 + 5; int n, a, b, da[N], db[N], d[N]; bool f[N]; vector<pii> g[N]; struct edge { int u, v, c; edge() { string f; cin >> u >> v >> f; --u, --v; c = 0; if(f[0] != 'c') c |= 1; if(f[0] != 'p') c |= 2; g[u].push_back({v, c}); g[v].push_back({u, c}); } }; vector<edge> es; void dijkstra(int *d, int s, int ms) { memset(d, 127, n << 2); d[s] = 0; queue<int> q; q.push(s); while(!q.empty()) { int v = q.front(); q.pop(); for(auto &i : g[v]) { if(!(i.sd & ms)) continue; int u = i.ft; if(d[u] <= d[v] + 1) continue; d[u] = d[v] + 1; q.push(u); } } } void solve() { #define ra return void(cout << "Paula\n") #define rb return void(cout << "Marin\n") #define rab return void(cout << "Magenta\n") cin >> n >> a >> b; --a, --b; for(int i = 0; i < n; ++i) g[i].clear(); es.clear(); for(int i = 1; i < n; ++i) es.emplace_back(); dijkstra(da, a, 1); dijkstra(db, b, 2); dijkstra(d, a, 3); bool was = false; for(auto &i : g[a]) if((i.sd & 1) && i.ft != b) was = true; if(!was) rb; was = false; for(auto &i : g[b]) if(i.sd & 2) was = true; if(!was) ra; if(d[b] & 1) { for(int i = 0; i < n; ++i) f[i] = da[i] < db[i]; for(auto &e : es) if(f[e.v] && f[e.u] && (e.c & 1) && db[e.v] > inf && db[e.u] > inf) rab; rb; } else { for(int i = 0; i < n; ++i) f[i] = db[i] < da[i]; for(auto &e : es) if(f[e.v] && f[e.u] && (e.c & 2) && da[e.v] > inf && da[e.u] > inf) rab; ra; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifndef _LOCAL // freopen("file.in", "r", stdin); // freopen("file.out", "w", stdout); #else system("color a"); freopen("in.txt", "r", stdin); int t; cin >> t; while(t--) #endif solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...