oj.uz

Submission #366337

# Submission time Handle Problem Language Result Execution time Memory
366337 2021-02-14T03:20:39 Z ajpiano Magenta (COCI21_magenta) C++17
30 / 110
 88 ms 7680 KB 
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

typedef long long ll;
typedef pair<int,int> pi;

const int large = 1e5+1;
const int inf = 1e9;
vector<pi> edges[large];

//Marin safe or Paula safe
bool ms = 0, ps = 0;

vector<int> distm, distp, d;

void df(int node, int par, int dist, vector<int> &cur, int bad){
    cur[node] = dist;
    for(auto &a: edges[node]){
        if(a.f == par) continue;
        if(a.s == bad) continue;
        df(a.f,node,dist+1,cur,bad);
    }

}
//inf node, found ans
bool draw(int node, int par, vector<int> &d1, vector<int> &d2, int add){
    bool found = 0;
    bool ans = 0;
    for(auto &a: edges[node]){
        if(a.f == par) continue;
        if(d1[a.f] == inf) continue;
        if(d1[a.f] >= d2[a.f]+add) continue;
        ans |= draw(a.f,node,d1,d2,add);
        found |= (d2[a.f] == inf);
    }
    if(d2[node] == inf && found == 1) ans = 1;
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    distm.resize(n+1, inf); distp.resize(n+1, inf); d.resize(n+1, inf);
    int a, b; cin >> a >> b;
    for(int i = 0; i < n-1; i++){
        int x,y; cin >> x >> y;
        string c; int col; cin >> c;
        if(c == "plava") col = 0;
        else if(c == "crvena") col = 1;
        else col = 2;
        edges[x].push_back({y,col});
        edges[y].push_back({x,col});
    }
    //check alone
    bool good = 0;
    for(auto &e: edges[a]){
        if(e.s != 1 && e.s != b){
            good = 1; break;
        }
    }
    if(!good){
        cout << "Marin\n"; return 0;
    }
    good = 0;
    for(auto &e: edges[b]){
        if(e.s != 0 && e.s != a){
            good = 1; break;
        }
    }
    if(!good){
        cout << "Paula\n"; return 0;
    }
    //fill out distances
    df(a,0,0,distp,1);
    df(b,0,0,distm,0);
    df(a,0,0,d,5);
    //check odd or even
    if(d[b]&1) ms = 1;
    else ps = 1;
    //check if draw
    if(ps == 0){
        bool ans = draw(a,0,distp,distm,1);
        if(ans == 0) cout << "Marin\n";
        else cout << "Magenta\n";
    }
    else if(ms == 0){
        bool ans = draw(b,0,distm,distp,0);
        if(ans == 0) cout << "Paula\n";
        else cout << "Magenta\n";
    }
    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 2796 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 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 88 ms 7532 KB Output is correct
2 Correct 81 ms 7532 KB Output is correct
3 Correct 88 ms 7660 KB Output is correct
4 Correct 81 ms 7680 KB Output is correct
5 Correct 78 ms 7532 KB Output is correct
6 Correct 2 ms 2688 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 2796 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Incorrect 2 ms 2668 KB Output isn't correct
8 Halted 0 ms 0 KB -