Submission #712593

#TimeUsernameProblemLanguageResultExecution timeMemory
712593vjudge1Dijamant (COI16_dijament)C++11
0 / 100
2 ms340 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]; bitset<MAXN> need[2]; vi g[MAXN], pg[MAXN], r[MAXN]; int nod = 1, pnod = 1, indeg[MAXN]; map<string, int> ids, pids; void failalo(){ FOR(i, 1, pnod) g[i] = pg[i]; nod = pnod; ids = pids; cout << "greska\n"; } void check(){ pids = ids; pnod = nod; FOR(i, 1, nod) pg[i] = g[i], indeg[i] = 0, r[i].clear(), cvis[i][0].reset(), cvis[i][1].reset(); string s = ""; while(s.empty()) getline(cin, s); string fir = ""; for(auto &x : s){ if(x == ' ') break; fir += x; } if(ids[fir]){ failalo(); return; } ids[fir] = nod++; vi sus; sus.clear(); int nid = fir.size() + 3; while(nid < s.size() - 1){ string cur = ""; while(s[nid] != ' ') cur += s[nid++]; nid++; if(ids[cur]) sus.PB(ids[cur]); else{ failalo(); return; } } for(auto &x : sus) g[x].PB(ids[fir]); FOR(j, 1, nod) for(auto &x : g[j]) indeg[x]++, r[x].PB(j); vi topo, st; topo.clear(), s.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; cin >> 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; }

Compilation message (stderr)

dijament.cpp: In function 'void check()':
dijament.cpp:76:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  while(nid < s.size() - 1){
      |        ~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...