Submission #253642

#TimeUsernameProblemLanguageResultExecution timeMemory
253642MrRobot_28Checker (COCI19_checker)C++17
110 / 110
1270 ms52456 KiB
#include<bits/stdc++.h> using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; int n; cin >> n; string s1; cin >> s1; map <pair <int, int>, int> mp; set <pair <int, int> >st1; for(int i = 0; i < n; i++) { st1.insert({i, (i + 1) % n}); mp[{i, (i + 1) % n}] = s1[i] - '0'; } set <pair <pair <int, int>, int> > s; vector <int> pr(n); vector <int> nxt(n); for(int i = 0; i < n; i++) { pr[i] = (i - 1 + n) % n; nxt[i] = (i + 1) % n; } queue <pair <pair <int, int>, int> > st; bool flag1 = 1; bool flag2 = 1; for(int i = 0; i < n - 3; i++) { int a, b, c; cin >> a >> b >> c; a--; b--; if(a == b || pr[a] == b || nxt[a] == b) { flag1 = 0; } if(nxt[nxt[a]] == b) { st.push({{a, b}, c}); } else if(pr[pr[a]] == b) { st.push({{b, a}, c}); } else { s.insert({{a, b}, c}); s.insert({{b, a}, c}); } } if(flag1) { while(st.size() != 0) { int a = st.front().first.first; int b = st.front().first.second; int c = st.front().second; st.pop(); if(nxt[nxt[a]] != b || st1.find({a, nxt[a]}) == st1.end() || st1.find({nxt[a], b}) == st1.end()) { flag1 = 0; break; } int kol1 = mp[{a, nxt[a]}]; int kol2 = mp[{nxt[a], b}]; if(kol1 == kol2 || kol1 == c || kol2 == c) { flag2 = 0; } st1.erase({a, nxt[a]}); st1.erase({nxt[a], b}); st1.insert({a, b}); mp[{a, b}] = c; nxt[a] = b; pr[b] = a; set <pair <pair <int, int>, int> > :: iterator it1, it2; it1 = s.lower_bound({{a, nxt[b]}, 0}); it2 = s.lower_bound({{pr[a], b}, 0}); if(it1 != s.end() && it1 -> first == make_pair(a, nxt[b])) { st.push({{a, nxt[b]}, it1 -> second}); s.erase({{it1 -> first.first, it1 -> first.second}, it1 -> second}); s.erase({{it1 -> first.second, it1 -> first.first}, it1 -> second}); } if(it2 != s.end() && it2 -> first == make_pair(pr[a], b)) { st.push(*it2); s.erase({{it2 -> first.first, it2 -> first.second}, it2 -> second}); s.erase({{it2 -> first.second, it2 -> first.first}, it2 -> second}); } } } if(s.size() != 0) { flag1 = 0; } if(!flag1) { cout << "neispravna triangulacija\n"; } else if(!flag2) { cout << "neispravno bojenje\n"; } else { cout << "tocno\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...