oj.uz

Submission #386461

# Submission time Handle Problem Language Result Execution time Memory
386461 2021-04-06T15:35:58 Z phathnv Magenta (COCI21_magenta) C++11
30 / 110
 92 ms 8320 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e5 + 1;
const int INF = 1e9 + 7;

struct Edge{
    int u, v, c;
    Edge(int _u, int _v, int _c){
        u = _u;
        v = _v;
        c = _c;
    }
};

int n, a, b;
vector<Edge> adj[N];

int dist[N], distFromA[N], distFromB[N];
bool vst[N];

int dfs(int u, int p, int dist[], int type){
    if (p == -1)
        dist[u] = 0;
    int res = 1;
    for(Edge e : adj[u])
        if (e.v != p && (e.c & type)){
            dist[e.v] = dist[u] + 1;
            res += dfs(e.v, u, dist, type);
        }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> a >> b;
    for(int i = 1; i < n; i++){
        int u, v, c;
        string s;
        cin >> u >> v >> s;
        if (s == "plava")
            c = 1;
        else if (s == "crvena")
            c = 2;
        else
            c = 3;
        adj[u].push_back(Edge(u, v, c));
        adj[v].push_back(Edge(v, u, c));
    }

    for(int i = 1; i <= n; i++)
        dist[i] = distFromA[i] = distFromB[i] = INF;

    dfs(a, -1, dist, 3);
    int numA = dfs(a, -1, distFromA, 1);
    int numB = dfs(b, -1, distFromB, 2);
    if (numA == 1){
        cout << "Marin\n";
        return 0;
    }
    if (numB == 1){
        cout << "Paula\n";
        return 0;
    }

    if (dist[b] % 2 == 0){
        queue<int> qu;
        vst[b] = 1;
        qu.push(b);
        while(!qu.empty()){
            int u = qu.front();
            qu.pop();
            for(Edge e : adj[u]){
                int v = e.v;
                int c = e.c;
                if (distFromB[v] < distFromA[v] && !vst[v] && (c & 2)){
                    vst[v] = 1;
                    qu.push(v);
                }
            }
        }
        for(int i = 1; i <= n; i++)
            vst[i] &= (distFromA[i] == INF);
        for(int u = 1; u <= n; u++)
            for(Edge e : adj[u])
                if (vst[u] && vst[e.v]){
                    cout << "Magenta";
                    return 0;
                }
        cout << "Paula";
    } else {
        queue<int> qu;
        vst[a] = 1;
        qu.push(a);
        while(!qu.empty()){
            int u = qu.front();
            qu.pop();
            for(Edge e : adj[u]){
                int v = e.v;
                int c = e.c;
                if (distFromA[v] <= distFromB[v] && !vst[v] && (c & 1)){
                    vst[v] = 1;
                    qu.push(v);
                }
            }
        }
        for(int i = 1; i <= n; i++)
            vst[i] &= (distFromB[i] == INF);
        for(int u = 1; u <= n; u++)
            for(Edge e : adj[u])
                if (vst[u] && vst[e.v]){
                    cout << "Magenta";
                    return 0;
                }
        cout << "Marin";
    }
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct
7 Incorrect 2 ms 2668 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 8300 KB Output is correct
2 Correct 92 ms 8172 KB Output is correct
3 Correct 86 ms 8300 KB Output is correct
4 Correct 91 ms 8172 KB Output is correct
5 Correct 85 ms 8320 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct
7 Incorrect 2 ms 2668 KB Output isn't correct
8 Halted 0 ms 0 KB -