| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 44922 |
2018-04-09T11:13:00 Z |
wasyl |
Ili (COI17_ili) |
C++11 |
|
2 ms |
564 KB |
#include <bits/stdc++.h>
#ifndef dbg
#define dbg(...)
#endif
#define all(x) begin(x), end(x)
#define rsz(...) resize(__VA_ARGS__)
#define psh(...) push_back(__VA_ARGS__)
#define emp(...) emplace_back(__VA_ARGS__)
#define prt(...) print(cout, __VA_ARGS__)
#define dmp(...) print(cerr, #__VA_ARGS__, '=', __VA_ARGS__)
#define dprt(...) dbg(print(cerr,__VA_ARGS__))
#define ddmp(...) dbg(dmp(__VA_ARGS__))
using namespace std;using ll=long long;
template<typename t>void print(ostream& os, const t& a){os<<a<<'\n';}
template<typename t, typename... A>void print
(ostream& os, const t& a, A&&... b){os<<a<<' ';print(os, b...);}
template<typename t>using V=vector<t>;
int n, m;
string s;
V< int > val;
V< bool > vis;
V< V< int > > gr;
V< V< int > > inp;
inline int query(int v, int s)
{
for (int r : inp[v])
if (r != s)
return r;
return INT_MIN;
}
inline int dfs(int v)
{
vis[v] = true;
if (val[v] == 1)
return 1;
for (int s : gr[v])
if (vis[s] == false and vis[query(s, v)] == true)
{
int r = dfs(s);
if (r == 1)
return 1;
if (r == 0)
{
val[v] = 0;
return 0;
}
}
if (val[v] == 0)
return 0;
int cnt = 0;
for (int p : inp[v])
if (p != -1 and vis[p] == false and val[p] == -1)
{
int r = dfs(p);
if (r == 1)
return 1;
if (r == 0)
++cnt;
}
return cnt == 2? 0 : -1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> s;
gr.rsz(n + m + 1);
vis.rsz(n + m + 1);
val.rsz(n + m + 1, -1);
inp.rsz(n + m + 1, V< int >(2, -1));
for (int i = n + 1; i <= n + m; ++i)
for (int k = 0; k < 2; ++k)
{
char c; int v;
cin >> c >> v;
int s = (c == 'c'? n : 0) + v;
inp[i][k] = s;
gr[s].psh(i);
}
queue< int > Q;
for (int i = n + 1; i <= n + m; ++i)
{
char c = s[i - n - 1];
if (c == '1' or c == '0')
val[i] = c - '0';
if (val[i] >= 0)
Q.push(i);
}
while (not Q.empty())
{
int v = Q.front(); Q.pop();
if (val[v] == 0)
for (int s : inp[v])
if (s != -1 and val[s] == -1)
val[s] = 0, Q.push(s);
for (int s : gr[v])
{
if (val[v] == 1)
if (val[s] == -1)
val[s] = 1, Q.push(s);
if (val[v] == 0)
{
int q = query(s, v);
if (val[s] == -1 and val[q] == 0)
val[s] = 0, Q.push(s);
if (val[s] == 1 and val[q] == -1)
val[q] = 1, Q.push(q);
}
}
}
for (int i = n + 1; i <= n + m; ++i)
fill(all(vis), false), val[i] = dfs(i);
for (int i = n + 1; i <= n + m; ++i)
cout << (val[i] >= 0? (char)(val[i] + '0') : '?');
cout << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Runtime error |
2 ms |
564 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Runtime error |
2 ms |
564 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Runtime error |
2 ms |
564 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
