Submission #712683

#TimeUsernameProblemLanguageResultExecution timeMemory
712683jcelinDijamant (COI16_dijament)C++14
56 / 100
2059 ms4156 KiB
#include <bits/stdc++.h> //#include<ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef long double ld; #define ii pair<int,int> #define pll pair<ll,ll> #define vi vector<int> #define vii vector<ii> #define vll vector<ll> #define vpll vector<pll> #define msi multiset<int> #define si set<int> #define PB push_back #define PF push_front #define PPB pop_back #define PPF pop_front #define X first #define Y second #define MP make_pair #define FOR(i, a, b) for (int i = int(a); i < int(b); i++) #define REP(i, n) FOR(i, 0, n) #define all(x) (x).begin(), (x).end() const int mod = 1e9 + 7; const int MOD = 998244353; const int inf = mod; const ll INF = 1e18; const int logo = 20; const int MAXN = 1e3 + 7; const int off = 1 << logo; const int trsz = off << 1; bitset<MAXN> cvis[MAXN][2], need[2]; vi g[MAXN], pg[MAXN], r[MAXN]; int nod = 1, pnod = 1, indeg[MAXN]; map<string, int> ids, pids; string fir; vi inp; vi topo, st, sus; void failalo(){ FOR(i, 1, nod + 1) g[i] = pg[i], pg[i].clear(), r[i].clear(), cvis[i][0].reset(), cvis[i][1].reset(), indeg[i] = 0; nod = pnod; ids.clear(); ids = pids; need[0].reset(); need[1].reset(); cout << "greska\n"; } void scan(int &a){ a=0; char c=getchar_unlocked(); while(c==10){ c=getchar_unlocked(); } while(c>='0' && c<='9'){ a*=10; a+=c-'0'; c=getchar_unlocked(); } } void scanline(){ fir.clear(); inp.clear(); char c = getchar_unlocked(); while(c==10){ c=getchar_unlocked(); } while(c != ' ') fir.PB(c), c = getchar_unlocked(); getchar_unlocked(); getchar_unlocked(); c = getchar_unlocked(); while(c==10){ c=getchar_unlocked(); } string s1; while(c != ';'){ while(c != ' ') s1.PB(c), c = getchar_unlocked(); inp.PB(ids[s1]); s1.clear(); c = getchar_unlocked(); } getchar_unlocked(); } void check(){ pids = ids; pnod = nod; FOR(i, 1, nod + 1){ pg[i] = g[i]; indeg[i] = 0; r[i].clear(); cvis[i][0].reset(); cvis[i][1].reset(); } scanline(); if(ids[fir]){ failalo(); return; } ids[fir] = nod++; for(auto &cur : inp){ if(!cur){ failalo(); return; } } for(auto &x : inp) g[x].PB(nod - 1); FOR(j, 1, nod) for(auto &x : g[j]) indeg[x]++, r[x].PB(j); vi topo, st; topo.clear(), st.clear(); FOR(j, 1, nod) if(indeg[j] == 0) st.PB(j); while(!st.empty()){ int u = st.back(); st.PPB(); topo.PB(u); for(auto &x : g[u]) if(--indeg[x] == 0) st.PB(x); } for(auto &x : topo){ cvis[x][0][x] = 1; for(auto &y : g[x]) cvis[y][0] |= cvis[x][0]; } reverse(all(topo)); for(auto &x : topo){ cvis[x][1][x] = 1; for(auto &y : r[x]) cvis[y][1] |= cvis[x][1]; } FOR(j, 1, nod) FOR(i, 1, j){ if(cvis[i][1][j] or cvis[i][0][j]) continue; need[0] = cvis[i][1] & cvis[j][1]; need[1] = cvis[i][0] & cvis[j][0]; need[0][i] = 0; need[0][j] = 0; need[1][i] = 0; need[1][j] = 0; if(need[0].count() and need[1].count()){ failalo(); return; } } cout << "ok\n"; } void solve(){ int n; scan(n); REP(i, n) check(); } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t=1; //cin >> t; while(t--)solve(); 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...