Submission #251644

#TimeUsernameProblemLanguageResultExecution timeMemory
251644kartelIli (COI17_ili)C++14
7 / 100
45 ms1536 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 +20500 #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 err ld(1e-9) #define last(x) x.back() #define all(x) (x).begin(), (x).end() #define arr_all(x, n) (x + 1), (x + 1 + n) 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; int c[N], n, m, i, j; string s; pair <int, int> pr[N]; bool mrk[N]; bitset<N> bt[N], clr; void go(int v) { c[v] = 1; int le = pr[v].F; int ri = pr[v].S; if (c[le] == 0 && c[ri] == -1) go(c[ri]); if (c[le] == -1 && c[ri] == 0) go(c[le]); } void push() { for (int i = n + m - 1; i >= n; i--) { if (c[i] != 1) continue; go(i); } } void dfs(int v) { c[v] = 0; if (v < n) return; mrk[v] = 1; if (!mrk[pr[v].F]) dfs(pr[v].F); if (!mrk[pr[v].S]) dfs(pr[v].S); } int main() { cout.precision(2); srand(time(0)); 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 >> n >> m; cin >> s; for (i = 0; i < n + m; i++) c[i] = -1, clr[i] = 0; for (i = n; i < n + m; i++) if (s[i - n] != '?') c[i] = s[i - n] - '0'; else c[i] = -1; for (i = 0; i < m; i++) { string f1, f2; cin >> f1 >> f2; int number = atoi(f1.substr(1).c_str()); if (f1[0] == 'c') number += n; number--; pr[i + n].F = number; number = atoi(f2.substr(1).c_str()); if (f2[0] == 'c') number += n; number--; pr[i + n].S = number; } while (1) { bool bad = 1; for (i = n; i < n + m; i++) { if (mrk[i]) continue; if (c[i] == 0) dfs(i); } for (i = n; i < n + m; i++) { if (c[pr[i].F] == 0 && c[pr[i].S] == 0 && c[i] == -1) c[i] = 0; if (c[i] == 0 && !mrk[i]) bad = 0; } if (bad) break; } for (i = n; i < n + m; i++) { bool gd = 0; queue <int> q; q.push(i); for (j = 0; j < n + m; j++) mrk[j] = 0; bt[i] = clr; while (sz(q)) { int v = q.front();q.pop(); if (v != i && c[v] == 1) gd = 1; if (i != v && c[v] != 0) bt[i][v] = 1; if (v < n) continue; if (!mrk[pr[v].F]) { mrk[pr[v].F] = 1; q.push(pr[v].F); } if (!mrk[pr[v].S]) { mrk[pr[v].S] = 1; q.push(pr[v].S); } } if (gd && c[i] == -1) c[i] = 1; } while (1) { push(); bool hv = 0; for (i = n; i < n + m; i++) { // cout << i << ":"; // for (j = 0; j < n + m; j++) cout << bt[i][j]; // cout << el; if (c[i] != -1) continue; bt[i][i] = 1; for (j = n; j < n + m; j++) if (i != j && c[j] == 1 && (bt[i] & bt[j]) == bt[j]) { hv = 1; c[i] = 1; } bt[i][i] = 0; } if (!hv) break; } for (i = n; i < n + m; i++) if (c[i] == -1) cout << "?"; else cout << c[i]; } // //00000 //00110 //00111 //00011 //00000
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...