Submission #206555

#TimeUsernameProblemLanguageResultExecution timeMemory
206555wiwihoChecker (COCI19_checker)C++14
110 / 110
471 ms51828 KiB
//#define NDEBUG #include <bits/stdc++.h> #include <bits/extc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define riter(a) a.rbegin(), a.rend() #define lsort(a) sort(iter(a)) #define gsort(a) sort(riter(a)) #define mp(a, b) make_pair(a, b) #define pb(a) push_back(a) #define eb(a) emplace_back(a) #define pf(a) push_front(a) #define pob pop_back() #define pof pop_front() #define F first #define S second #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; pvaspace=true;\ b << pva;\ }\ b << "\n";} #define pii pair<int, int> #define pll pair<ll, ll> #define tiii tuple<int, int, int> #define mt make_tuple #define gt(t, i) get<i>(t) #define iceil(a, b) ((a) / (b) + !!((a) % (b))) //#define TEST typedef long long ll; typedef unsigned long long ull; using namespace std; using namespace __gnu_pbds; const ll MOD = 1000000007; const ll MAX = 2147483647; template<typename A, typename B> ostream& operator<<(ostream& o, pair<A, B> p){ return o << '(' << p.F << ',' << p.S << ')'; } int main(){ StarBurstStream string nos = "neispravna triangulacija\n"; string nop = "neispravno bojenje\n"; string isp = "tocno\n"; int T; cin >> T; int n; cin >> n; string s; cin >> s; vector<map<int, int>> g(n + 1); vector<int> deg(n + 1); for(int i = 1; i <= n; i++){ int j = i + 1 > n ? 1 : i + 1; g[i][j] = s[i - 1] - '0'; g[j][i] = s[i - 1] - '0'; deg[i]++; deg[j]++; } for(int i = 0; i < n - 3; i ++){ int u, v, c; cin >> u >> v >> c; if(g[u].find(v) != g[u].end()) return cout << nos, 0; deg[u]++; deg[v]++; g[u][v] = c; g[v][u] = c; } queue<int> q; vector<bool> no(n + 1); int cnt = 0; for(int i = 1; i <= n; i++) if(deg[i] == 2) q.push(i); int ans = 2; while(!q.empty()){ // cerr << "test\n"; if(cnt == n - 2) break; int now = q.front(); // cerr << now << "\n"; q.pop(); no[now] = true; if(deg[now] != 2){ ans = 0; break; } vector<int> v; for(pii i : g[now]){ // cerr << "test " << i << "\n"; if(!no[i.F]) v.eb(i.F); } // printv(v, cerr); if(g[v[0]].find(v[1]) == g[v[0]].end()){ ans = 0; break; } if(g[v[0]][v[1]] == g[now][v[0]] || g[v[0]][v[1]] == g[now][v[1]] || g[now][v[0]] == g[now][v[1]]){ ans = 1; } deg[v[0]]--; deg[v[1]]--; if(deg[v[0]] == 2) q.push(v[0]); if(deg[v[1]] == 2) q.push(v[1]); cnt++; // cerr << "test\n"; } int tmp = 0; for(int i = 1; i <= n; i++) if(!no[i]) tmp++; if(tmp != 2) ans = 0; if(ans == 0) cout << nos; else if(ans == 1) cout << nop; else cout << isp; 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...