| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 66402 |
2018-08-10T11:49:47 Z |
MrTEK |
Ili (COI17_ili) |
C++14 |
|
5 ms |
3112 KB |
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left ind+ind
#define right ind+ind+1
#define mid (l+r)/2
#define FAST_IO ios_base::sync_with_stdio(false);
#define endl '\n'
typedef long long int ll;
const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 1e4 + 5;
const int M = 1e4 + 5;
const int SQ = 350;
const int MOD = 998244353;
typedef pair <int,int> pii;
int n,m,val[M],vis[M];
vector <int> ed[M],red[M],v[M],ned[M],rned[M];
void pre_dfs(int cur) {
if (vis[cur]) return;
vis[cur] = 1;
for (auto i : red[cur]) {
if (i > m) v[cur].pb(i);
else {
pre_dfs(i);
for (auto j : v[i]) v[cur].pb(j);
}
}
}
void solve(int cur) {
if (vis[cur]) return;
vis[cur] = 1;
if (cur > m) return;
int ch1 = red[cur][0],ch2 = red[cur][1];
if (val[cur] == 1 && val[ch1] == -1 && val[ch2] == 0) val[ch1] = 1;
if (val[cur] == 1 && val[ch2] == -1 && val[ch1] == 0) val[ch2] = 1;
if (val[cur] == 0) val[ch1] = val[ch2] = 0;
solve(ch1);
solve(ch2);
}
void dfs(int cur) {
if (vis[cur]) return;
vis[cur] = 1;
for (auto i : ned[cur]) {
dfs(i);
if (val[i] == 0) val[cur] = 0;
}
}
void dfs2(int cur) {
if (vis[cur]) return;
vis[cur] = 1;
for (auto i : rned[cur]) {
dfs2(i);
if (val[i] == 1) val[cur] = 1;
}
}
int main() {
scanf("%d %d",&n,&m);
memset(val,-1,sizeof val);
for (int i = 1 ; i <= m ; i++) {
char c;
scanf(" %c",&c);
if (c == '1') val[i] = 1;
else if (c == '0') val[i] = 0;
else val[i] = -1;
}
for (int i = 1 ; i <= m ; i++) {
char c1,c2,c3,c4;
scanf(" %c %c %c %c",&c1,&c2,&c3,&c4);
int n1 = c2 - '0' + (c1 == 'x' ? m : 0), n2 = c4 - '0' + (c3 == 'x' ? m : 0);
ed[n1].pb(i);
ed[n2].pb(i);
red[i].pb(n1);
red[i].pb(n2);
}
for (int i = 1 ; i <= m ; i++) pre_dfs(i);
for (int i = 1 ; i <= m ; i++) {
sort(v[i].begin(),v[i].end());
v[i].resize(unique(v[i].begin(),v[i].end()) - v[i].begin());
}
for (int i = 1 ; i <= m ; i++) {
for (int j = i + 1 ; j <= m ; j++) {
int x = i , y = j;
if (len(v[x]) > len(v[y])) swap(x,y);
bool flag = true;
for (auto k : v[x]) {
int tut = lower_bound(v[y].begin(),v[y].end(),k) - v[y].begin();
if (y < len(v[y]) || v[y][tut] != k) {flag = false;break;}
}
if (flag) ned[x].pb(y);
if (flag) rned[y].pb(x);
}
}
for (int asd = 0; asd < 2; asd++) {
memset(vis,0,sizeof vis);
for (int i = 1 ; i <= m; i++) solve(i);
}
for (int i = 1 ; i <= m ; i++) {
int flag = 0;
for (auto j : v[i]) {
if (val[j] == -1) flag = -1;
if (val[j] == 1) {flag = 1; break;}
}
if (val[i] == -1) val[i] = flag;
}
// for (int i = 1 ; i <= m ; i++) {
// if (val[i] == 1) printf("1");
// else if(val[i] == 0) printf("0");
// else printf("?");
// }
// puts("");
memset(vis,0,sizeof vis);
for (int i = 1 ; i <= m ; i++) dfs(i);
memset(vis,0,sizeof vis);
for (int i = 1 ; i <= m ; i++) dfs2(i);
for (int i = 1 ; i <= m ; i++) {
if (val[i] == 1) printf("1");
else if(val[i] == 0) printf("0");
else printf("?");
}
}
Compilation message
ili.cpp: In function 'int main()':
ili.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
ili.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&c);
~~~~~^~~~~~~~~~
ili.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c %c %c %c",&c1,&c2,&c3,&c4);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1528 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1664 KB |
Output is correct |
| 3 |
Runtime error |
5 ms |
3112 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 |
3 ms |
1528 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1664 KB |
Output is correct |
| 3 |
Runtime error |
5 ms |
3112 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 |
3 ms |
1528 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1664 KB |
Output is correct |
| 3 |
Runtime error |
5 ms |
3112 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
