Submission #400048

#	Time	Username	Problem	Language	Result	Execution time	Memory
400048		jenkinsser	Magenta (COCI21_magenta)	C++17	110 / 110	84 ms	11076 KiB

Main

#include <bits/stdc++.h>
#define FOR(ii,aa,bb) for(int ii=aa;ii<bb;ii++)
#define for0(ii,bb) FOR(ii,0,bb)
#define for1(ii,bb) FOR(ii,1,bb+1)
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<int,int>
#define piii pair<int,pii>
#define pdi pair<double,int>
#define vi vector<int>
#define sp " "
#define nl "\n"
#define all(x) x.begin(),x.end()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define int ll

using namespace std;

const int N = 1e5+5;
const int INF = 1e9+5;
const int mod = 998244353;

int n,s[2],can_move[2],dist[N][2],len,kacan;
vector<pii> g[N];

string str[3]={"Paula","Marin","Magenta"};
map<string,int> col;

void dfs(int v,int p,int x){
    for(auto e:g[v]){
        if(e.st==p)continue;
        if(e.st==s[x^1])
            len=dist[v][x]+1;
        if(e.nd!=(x^1)){
            dist[e.st][x]=dist[v][x]+1;
            dfs(e.st,v,x);
        }
    }
}

bool check(int v,int p=-1){
    bool ok=false;
    for(auto e:g[v]){
        if(e.st==p||e.nd==(kacan^1)||(dist[e.st][kacan^1]!=-1&&dist[e.st][kacan]>=dist[e.st][kacan^1]))
            continue;
        if(dist[e.st][kacan^1]==-1&&dist[v][kacan^1]==-1)
            return true;
        ok|=check(e.st,v);
    }
    return ok;
}

void print(int x){
    cout << str[x] << nl;
    exit(0);
}

signed main(){
    fastio()
    col["plava"]=0;
    col["crvena"]=1;
    col["magenta"]=2;
    cin >> n >> s[0] >> s[1];
    for(int i=1;i<n;i++){
        int u,v;
        string t;
        cin >> u >> v >> t;
        int c=col[t];
        g[u].pb({v,c});
        g[v].pb({u,c});
        if(c!=1&&((s[0]==u&&s[1]!=v)||(s[0]==v&&s[1]!=u)))
            can_move[0]=1;
        if(c!=0&&(s[1]==u||s[1]==v))
            can_move[1]=1;
    }
    if(!can_move[0])
        print(1);
    if(!can_move[1])
        print(0);
    memset(dist,-1,sizeof(dist));
    dist[s[0]][0]=0;
    dfs(s[0],-1,0);
    dist[s[1]][1]=0;
    dfs(s[1],-1,1);
    kacan=(len+1)%2;
    if(check(s[kacan]))
        print(2);
    print(kacan^1);
}

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