oj.uz

Submission #375219

# Submission time Handle Problem Language Result Execution time Memory
375219 2021-03-09T04:40:43 Z Kalashnikov Magenta (COCI21_magenta) C++17
0 / 110
 296 ms 25196 KB 
#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
 
using namespace std;
using ll = long long;
 
const int N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7 , P = 6547;

vector<pair<int,string>> g[N];

set<int> st[2];
int ca , cnt = 0;
int toE[2] , dist;

void dfs(int v, const string s , int p = 0 , int dst = 0) {
	//cout << v << '\n';
	if(s == "plava") {
		st[0].insert(v);
	}
	else {
		st[1].insert(v);
	}
	for(auto x: g[v]) {
		int to = x.F;
		string t = x.S;
		if(to != p && (t == s || t == "magenta") && to != ca) {
			dfs(to , s , v , dst+1);
		}
		if(to == ca) {
			dist = dst+1;
			if(s == "plava")
				toE[0] = 1;
			else {
				toE[1] = 1;
			}
		}
	}
}

void solve() {
	int n;
	cin >> n;
	int a , b;
	cin >> a >> b;
	for(int i = 1; i < n; i ++) {
		int a , b;
		cin >> a >> b;
		string s;
		cin >> s;
		g[a].push_back({b , s});
		g[b].push_back({a , s});
	}
	ca = b; dfs(a , "plava");
	ca = a; dfs(b , "crvena");
	if(st[0].size() == 1) {
		cout << "Marin";
		return;
	}
	// if(st[1].size() == 1) {
		// cout << "Paula1";
		// return;
	// }	
	
//	cout << toE[0] << ' ' << toE[1] << '\n';
	
	if(toE[0] + toE[1] == 0) {
		cout << "Magenta";
		return;
	}
	//cout << dist << '\n';
	if(dist % 2 == 0 && toE[0]) {
		if(rand()%2) {
				cout << "Paula";
			return;
		}
	}
	if(dist % 2 == 1 && toE[1]) {
		if(rand()%2) {
			cout << "Marin";
			return;
		}
	}
	
	cout << "Magenta";
}
/*
*/
main() {
	srand(time(0));
   // ios;
    int tt = 1;
    //cin >> tt;
    while(tt --) {
        solve();
    }
    return 0;
}

Compilation message

Main.cpp:94:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   94 | main() {
      |      ^

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Incorrect 4 ms 4972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 24520 KB Output is correct
2 Incorrect 296 ms 25196 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Incorrect 4 ms 4972 KB Output isn't correct
4 Halted 0 ms 0 KB -