Submission #367626

#	Time	Username	Problem	Language	Result	Execution time	Memory
367626		MrRobot_28	Magenta (COCI21_magenta)	C++17	110 / 110	87 ms	7272 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
map <string, int> col = {
    {"plava", 0},
    {"crvena", 1},
    {"magenta", 2}
};
const int N = 1e5 + 100;
int n;
int dist[2][N];
vector <pair <int, int> > g[N];
vector <string> names = {"Paula", "Marin", "Magenta"};
int move_to[2];
    vector <int> s;
void print(int a)
{
    cout << names[a];
}
int len;
void dfs(int v, int i, int p = -1)
{
    for(int j = 0; j < g[v].size(); j++)
    {
        int to = g[v][j].X;
        int type = g[v][j].Y;
        if(to == p)
        {
            continue;
        }
        if(to == s[i ^ 1])
        {
            len = dist[i][v] + 1;
        }
        if(type != (i ^ 1))
        {
            dist[i][to] = dist[i][v] + 1;
            dfs(to, i, v);
        }
    }
}
int val;
bool funct(int v, int p =-1)
{
    bool fl = 0;
    for(int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i].X;
        int w = g[v][i].Y;
        if(to == p || w == (val ^ 1) || dist[val ^ 1][to] != 1e9 && dist[val][to] >= dist[val ^ 1][to])
        {
            continue;
        }
        if(dist[val ^ 1][v]== 1e9 && dist[val ^ 1][to] == 1e9)
        {
            return 1;
        }
        fl |= funct(to, v);
    }
    return fl;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    s = {a, b};
    for(int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        string s;
        cin >> s;
        int type = col[s];
        g[u].push_back({v, type});
        g[v].push_back({u, type});
        if(type != 1 && (u == a && v != b || v == a && u != b))
        {
            move_to[0] = 1;
        }
        if(type != 0 && (u == b || v == b))
        {
            move_to[1] = 1;
        }
    }
    if(!move_to[0])
    {
        print(1);
        return 0;
    }
    if(!move_to[1])
    {
        print(0);
        return 0;
    }
    for(int i = 0; i < 2; i++)
    {
        int st = s[i];
        fill(dist[i], dist[i] + N, 1e9);
        dist[i][s[i]] = 0;
        dfs(s[i], i);
    }
    val = (len + 1) % 2;
    if(funct(s[val], -1))
    {
        print(2);
        return 0;
    }
    print(1 - val);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(int, int, int)':
Main.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int j = 0; j < g[v].size(); j++)
      |                    ~~^~~~~~~~~~~~~
Main.cpp: In function 'bool funct(int, int)':
Main.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i = 0; i < g[v].size(); i++)
      |                    ~~^~~~~~~~~~~~~
Main.cpp:51:66: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   51 |         if(to == p || w == (val ^ 1) || dist[val ^ 1][to] != 1e9 && dist[val][to] >= dist[val ^ 1][to])
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:85:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   85 |         if(type != 1 && (u == a && v != b || v == a && u != b))
      |                          ~~~~~~~^~~~~~~~~
Main.cpp:106:13: warning: unused variable 'st' [-Wunused-variable]
  106 |         int st = s[i];
      |             ^~

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