Submission #366394

#	Time	Username	Problem	Language	Result	Execution time	Memory
366394		faustaadp	Magenta (COCI21_magenta)	C++17	30 / 110	160 ms	57344 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int NN = 1e6 + 5;
const int mo = 1e9 + 7;
const ld eps = 1e-9;
ll n, a, b;
vector<ll> v[NN];
vector<ll> w[NN];
ll A = 0;
ll B = 0;
ll dis[4][NN];
ll rg[4];
void dfs(ll pos, ll par, ll jen, ll jar)
{
    // rg[jen]++;
    // if(jen == 2)
        // rg[2]++;
    dis[jen][pos] = jar;
    for(ll i = 0; i < v[pos].size(); i++)
        if((v[pos][i] != par) && (w[pos][i] & jen))
            dfs(v[pos][i], pos, jen, jar + 1);
}
void dfs1(ll pos, ll par)
{
    if(dis[2][pos] < dis[1][pos])
        return ;
    // rg[1]++;
    if(dis[2][pos] == 1e18)
    {
        for(ll i = 0; i < v[pos].size(); i++)
            if(dis[2][v[pos][i]] == 1e18)
                A = 1;
        for(ll i = 0; i < v[pos].size(); i++)
            if((dis[2][v[pos][i]] % 2) == (dis[1][v[pos][i]] % 2))
                A = 1;
    }
    for(ll i = 0; i < v[pos].size(); i++)
        if((v[pos][i] != par) && (w[pos][i] & 1))
            dfs1(v[pos][i], pos);
}
void dfs2(ll pos, ll par)
{
    if(dis[1][pos] <= dis[2][pos])
        return ;
    // rg[2]++;
    if(dis[1][pos] == 1e18)
    {
        for(ll i = 0; i < v[pos].size(); i++)
            if(dis[1][v[pos][i]] == 1e18)
                B = 1;
        for(ll i = 0; i < v[pos].size(); i++)
            if((dis[1][v[pos][i]] % 2) != (dis[2][v[pos][i]] % 2))
                B = 1;
    }
    for(ll i = 0; i < v[pos].size(); i++)
        if((v[pos][i] != par) && (w[pos][i] & 2))
            dfs2(v[pos][i], pos);
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> a >> b;
    for(ll i = 1; i <= n; i++)
    {
        dis[1][i] = 1e18;
        dis[2][i] = 1e18;
    }
    for(ll i = 1; i < n; i++)
    {
        ll ta, tb, tc = 3;
        string s;
        cin >> ta >> tb >> s;
        if(s == "plava")tc = 1;
        else if(s == "crvena")tc = 2;
        v[ta].pb(tb);
        w[ta].pb(tc);
        v[tb].pb(ta);
        w[tb].pb(tc);
    }
    dfs(a, a, 1, 0);
    dfs(b, b, 2, 0);
    dfs(a, a, 3, 0);
    dfs1(a, a);
    dfs2(b, b);
    // if(A == 0 && B == 0)
    // {
    //     if(dis[1][b])
    // }
    // cout << rg[1] << "  " << rg[2] << "\n";
   
    // cout << A << " " << B << " " << dis[3][b] << "@\n" << "\n";
    if(rg[1] == 1 || n == 2)
        cout << "Marin\n";
    else
    if(rg[2] == 1)
        cout << "Paula\n";
    else
    if(((dis[3][b] % 2 == 0) && (dis[3][b] != 1e18)) && (B == 0))
        cout << "Paula\n";
    else
    if((dis[3][b] % 2 == 1) && (A == 0))
        cout << "Marin\n";
    else
        cout << "Magenta\n";
}
    

Compilation message (stderr)

Main.cpp: In function 'void dfs(ll, ll, ll, ll)':
Main.cpp:25:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(ll i = 0; i < v[pos].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void dfs1(ll, ll)':
Main.cpp:36:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(ll i = 0; i < v[pos].size(); i++)
      |                       ~~^~~~~~~~~~~~~~~
Main.cpp:39:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(ll i = 0; i < v[pos].size(); i++)
      |                       ~~^~~~~~~~~~~~~~~
Main.cpp:43:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(ll i = 0; i < v[pos].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~
Main.cpp: In function 'void dfs2(ll, ll)':
Main.cpp:54:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(ll i = 0; i < v[pos].size(); i++)
      |                       ~~^~~~~~~~~~~~~~~
Main.cpp:57:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(ll i = 0; i < v[pos].size(); i++)
      |                       ~~^~~~~~~~~~~~~~~
Main.cpp:61:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(ll i = 0; i < v[pos].size(); i++)
      |                   ~~^~~~~~~~~~~~~~~

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