Submission #1135410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135410		khanhgng	Magenta (COCI21_magenta)	C++20	110 / 110	37 ms	14152 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define ld long double
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define bit(i, x) ((x >> i) & 1)
#define SZ(x) ((int)(x.size()))
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define task "test"

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }

const int MAXn = 3e5+10;
const ll INF = (long long)(1e18);
const int MOD = 1e9 + 7;
const int BASE = 3137;
const int BL = 450;

int n,s[2],ok[2],dist[MAXn][2],kc,unsafe;
vector<pii>adj[MAXn];

int color(string str){
    if(str=="plava")return 0;
    if(str=="crvena")return 1;
    return 2;
}

string prt(int x){
    if(x==0)return "Paula";
    else if(x==1)return "Marin";
    return "Magenta";
}

void dfs(int u,int par,int state){
    for(pii tmp:adj[u]){
        int v=tmp.fi;
        int c=tmp.se;
        if(v==par)continue;
        if(v==s[state^1])kc=dist[u][state]+1;
        if(c!=(state^1)){
            dist[v][state]=dist[u][state]+1;
            dfs(v,u,state);
        }
    }
}

bool issafe(int u,int par,int state){
    bool ans=0;
    for(pii tmp:adj[u]){
        int v=tmp.fi;
        int c=tmp.se;
        if(v==par||c==(state^1)||(dist[v][state^1]!=-1&&dist[v][state^1]<=dist[v][state]))continue;
        if(dist[v][state^1]==-1&&dist[u][state^1]==-1)return 1;
        ans|=issafe(v,u,state);
    }
    return ans;
}

void solution() {
    cin>>n>>s[0]>>s[1];
    FOR(i,1,n){
        int u,v,c;cin>>u>>v;
        string col;cin>>col;
        c=color(col);
        adj[u].pb({v,c});
        adj[v].pb({u,c});
        if(c!=1&&(u==s[0]&&v!=s[1]||u!=s[1]&&v==s[0]))ok[0]=1;
        if(c!=0&&(u==s[1]||v==s[1]))ok[1]=1;
    }
    if(!ok[0]){cout<<prt(1);return;}
    if(!ok[1]){cout<<prt(0);return;}
    FOR(i,1,n)dist[i][0]=-1,dist[i][1]=-1;
    dist[s[0]][0]=0;
    dist[s[1]][1]=0;
    dfs(s[0],0,0);
    dfs(s[1],0,1);
    unsafe=((kc+1)&1);
    if(issafe(s[unsafe],0,unsafe)){cout<<prt(2);return;}
    cout<<prt(unsafe^1);
}

int32_t main() {
    if (fopen(task".inp", "r")){freopen(task".inp", "r", stdin);freopen(task".out", "w", stdout);}
    ios::sync_with_stdio(0); cin.tie(0);
    int ntest = 1; ///cin >> ntest;
    while (ntest--) solution();
    cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:90:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     if (fopen(task".inp", "r")){freopen(task".inp", "r", stdin);freopen(task".out", "w", stdout);}
      |                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:90:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     if (fopen(task".inp", "r")){freopen(task".inp", "r", stdin);freopen(task".out", "w", stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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