Submission #268045

#TimeUsernameProblemLanguageResultExecution timeMemory
268045kartelDijamant (COI16_dijament)C++14
13 / 100
1874 ms42104 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("Ofast,nso-stack-protector,unroll-loops,fast-math,-O3") #define F first #define S second #define pb push_back #define N +300500 #define M ll(1e9 + 7) #define sz(x) (int)x.size() #define re return #define oo ll(1e9) #define el '\n' #define Max_A int(1e9) //#define el endl #define pii pair <int, int> #define piii pair <int, pair <int, int> > #define psi pair <string, int> #define err ld(1e-9) #define Max_S int(3e6) #define last(x) x.back() #define all(x) (x).begin(), (x).end() #define allr(x) (x).rbegin(), (x).rend() #define arr_all(x, n) (x + 1), (x + 1 + n) #define vi vector<int> using namespace std; //using namespace __gnu_pbds; //typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef long long ll; typedef long double ld; map <string, int> mp; int q, id; string k, s; int mrk[N]; vector <int> g[N], G[N], prd[N], pred[N]; void check_cycles(int v, bool &bad) { if (bad) return; if (mrk[v] == 1) { bad = 1; return; } if (mrk[v] == 2) return; mrk[v] = 1; for (auto u : G[v]) { if (bad) return; check_cycles(u, bad); } mrk[v] = 2; } void dfs(int v) { if (mrk[v]) return; mrk[v] = 1; for (auto u : prd[v]) dfs(u); } void up(int v, bool &bad, bool &vis) { if (vis) return; if (mrk[v] == 2) { vis = 1; return; } if (mrk[v] == 1) { bad = 1; return; } for (auto u : prd[v]) { if (bad) return; up(u, bad, vis); } } int main() { // srand(time(0)); cout.precision(3); cout << fixed; ios_base::sync_with_stdio(0); iostream::sync_with_stdio(0); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); // in("input.txt"); // out("output.txt"); cin >> q; id = 0; while (q--) { bool bad = 0; cin >> k; if (mp.find(k) == mp.end()) mp[k] = id++; else bad = 1; vector <string> vec; cin >> s >> s; int kol = 0; while (s != ";") { kol++; vec.pb(s); if (mp.find(s) == mp.end()) bad = 1; cin >> s; } sort(all(vec)); int i = 1; while (i < sz(vec) && vec[i - 1] != vec[i]) i++; bad = (bad | (i < sz(vec))); if (!bad) { for (int i = 0; i < id; i++) G[i] = g[i], prd[i] = pred[i], mrk[i] = 0; for (auto s : vec) { prd[mp[k]].pb(mp[s]); G[mp[s]].pb(mp[k]); } for (int i = 0; i < id; i++) if (!mrk[i] && !bad && sz(prd[i]) == 0) check_cycles(i, bad); // if (!bad) // { // for (auto p : prd[mp[k]]) // { // for (int i = 0; i < id; i++) // mrk[i] = 0; // // mrk[p] = 2; // // for (auto p1 : prd[p]) // dfs(p1); // // for (auto p1 : prd[mp[k]]) // { // if (p1 == p || mrk[p1] || bad) // continue; // // for (auto p2 : prd[p1]) // { // if (bad) // break; // // bool vis = 0; // up(p2, bad, vis); // // if (vis) // bad = 0; // } // } // // if (bad) // break; // } // } } if (!bad) { for (auto s : vec) { pred[mp[k]].pb(mp[s]); g[mp[s]].pb(mp[k]); } } cout << (bad ? "greska" : "ok") << el; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...