Submission #368023

#TimeUsernameProblemLanguageResultExecution timeMemory
368023egekabasMagenta (COCI21_magenta)C++14
30 / 110
145 ms13164 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define ff first #define ss second #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ull, ull> pull; typedef pair<int, int> pii; typedef pair<ld, ld> pld; int n; vector<int> g[100009][2]; int reach[100009][2]; int dis[1000009][2]; void dfs(int v, int col){ reach[v][col] = 1; for(auto u : g[v][col]) if(reach[u][col] == 0) dfs(u, col); } void calcdis(int v, int col){ for(auto u : g[v][0]) if(dis[u][col] == 1e9){ dis[u][col] = dis[v][col]+1; calcdis(u, col); } for(auto u : g[v][1]) if(dis[u][col] == 1e9){ dis[u][col] = dis[v][col]+1; calcdis(u, col); } } int st[2]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); cin >> n; cin >> st[0] >> st[1]; for(int i = 0; i < n-1; ++i){ int x, y; cin >> x >> y; string s; cin >> s; if(s == "plava" || s == "magenta"){ g[x][0].pb(y); g[y][0].pb(x); } if(s == "crvena" || s == "magenta"){ g[x][1].pb(y); g[y][1].pb(x); } } for(int i = 1; i <= n; ++i) dis[i][0] = dis[i][1] = 1e9; dfs(st[0], 0); dfs(st[1], 1); dis[st[0]][0] = 0; dis[st[1]][1] = 0; calcdis(st[0], 0); calcdis(st[1], 1); int winner; if(dis[st[0]][1]%2) winner = 1; else winner = 0; int loser = winner^1; int draw = 0; if(g[st[0]][0].empty()){ cout << "Marin\n"; return 0; } if(g[st[1]][1].empty()){ cout << "Paula\n"; return 0; } if(reach[st[loser]][winner] == 0){ cout << "Magenta\n"; return 0; } for(int i = 1; i <= n; ++i){ if(reach[i][winner] || dis[i][winner] <= dis[i][loser]) continue; if(reach[i][loser] == 0) continue; int ok = 0; for(auto u : g[i][loser]){ if(reach[u][winner] || dis[u][winner] <= dis[u][loser]) continue; if(reach[u][loser] == 0) continue; ok = 1; } if(ok) draw = 1; } if(draw) cout << "Magenta\n"; else if(winner == 0) cout << "Paula\n"; else cout << "Marin\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...