| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 377698 |
2021-03-14T19:03:15 Z |
Sara |
Ili (COI17_ili) |
C++14 |
|
1 ms |
876 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define F first
#define S second
#define pb push_back
const int N = 20000 + 10;
const int LOG = 25;
const int MOD = 1e9 + 7;
const ll inf = 1e9 + 5;
int n, m;
string a;
int ans[N];
int tmp[N];
int help[N];
vector <int> adj[N];
pair <int, int> e[N];
void dfs_set0(int v){
tmp[v] = -1;
if (v <= n) return;
for (int u : adj[v]){
dfs_set0(u);
}
return;
}
inline bool ok(int v){
for (int i = 1; i <= n + m; i ++){
tmp[i] = 1;
}
for (int i = 1; i <= n + m; i ++){
if (ans[i] == -1){
tmp[i] = -1;
}
}
dfs_set0(v);
for (int i = 1; i <= m; i ++){
int par = i + n;
int u = e[i].F;
int v = e[i].S;
if ((tmp[u] == 1) || (tmp[v] == 1)){
tmp[par] = 1;
}
else {
assert((tmp[u] == -1) && (tmp[v] == -1));
tmp[par] = -1;
}
if ((tmp[par] == 1) && (a[i] == '0')) return 0;
if ((tmp[par] == -1) && (a[i] == '1')) return 0;
}
return 1;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0);
cin >> n >> m >> a;
a = ' ' + a;
for (int i = 1; i <= n + m; i ++){
ans[i] = 1;
}
for (int i = 1; i <= m; i ++){
char type;
int u, v, par = i + n;
cin >> type >> u;
if (type == 'c') u += n;
cin >> type >> v;
if (type == 'c') v += n;
adj[par].pb(u);
adj[par].pb(v);
e[i] = {u, v};
}
for (int i = m; i >= 1; i --){
int par = i + n;
if (a[i] != '0') continue;
ans[i + n] = -1;
for (int u : adj[par]){
if (n < u){
a[u - n] = '0';
}
ans[u] = -1;
}
}
for (int i = 1; i <= m; i ++){
if ((ans[i + n] == 1) && (a[i] == '?')){
a[i] = '0';
ans[i + n] = 1 - ok(i + n);
a[i] = '?';
}
if (ans[i + n] == 1) cout << 1;
if (ans[i + n] == -1) cout << 0;
if (ans[i + n] == 0) cout << '?';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
876 KB |
Output is correct |
| 2 |
Correct |
1 ms |
876 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
876 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
876 KB |
Output is correct |
| 2 |
Correct |
1 ms |
876 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
876 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
876 KB |
Output is correct |
| 2 |
Correct |
1 ms |
876 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
876 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
