| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 782353 |
2023-07-13T20:50:46 Z |
MasterTaster |
Ili (COI17_ili) |
C++14 |
|
1 ms |
980 KB |
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
#define MAXN 10010
using namespace std;
int n, m, ress[MAXN], cnt[MAXN];
bool bio[MAXN], dal0[MAXN];
vector<int> g[2][MAXN], guk[MAXN];
void dfs(int t, int u)
{
bio[u]=true;
for (auto v:g[t][u]) if (!bio[v]) dfs(t, v);
}
int main(){
cin>>n>>m;
string s; cin>>s;
queue<int> q;
for (int i=0; i<n+m; i++) ress[i]=-1;
for (int i=0; i<s.size(); i++) if (s[i]!='?') { ress[i+n]=s[i]-'0'; if (ress[i+n]==0) q.push(i+n); }
for (int i=0; i<m; i++)
{
string s1, s2; cin>>s1>>s2;
int a, b;
if (s1[0]=='x')
{
string pom=s1.substr(1, s1.size()-1);
a=stoi(pom)-1;
}
else
{
string pom=s1.substr(1, s1.size()-1);
a=stoi(pom)-1+n;
}
if (s2[0]=='x')
{
string pom=s2.substr(1, s2.size()-1);
b=stoi(pom)-1;
}
else
{
string pom=s2.substr(1, s2.size()-1);
b=stoi(pom)-1+n;
}
g[0][a].pb(i+n); g[1][i+n].pb(a);
g[0][b].pb(i+n); g[1][i+n].pb(b);
guk[a].pb(i+n); guk[i+n].pb(a);
guk[b].pb(i+n); guk[i+n].pb(b);
//cout<<a<<" "<<i+n<<endl;
//cout<<b<<" "<<i+n<<endl;
}
while (!q.empty())
{
int u=q.front();
q.pop();
//cout<<u<<endl;
for (auto v:guk[u])
{
if (v>u) cnt[v]++;
if ((v<u || cnt[v]>=2) && !bio[v]) { bio[v]=true; ress[v]=0; q.push(v); }
}
}
for (int i=0; i<n; i++) if (ress[i]==-1) ress[i]=1;
for (int i=0; i<m; i++) if (ress[i+n]==-1) dal0[i+n]=1;
for (int i=0; i<n+m; i++) bio[i]=false;
for (int i=0; i<m; i++)
{
if (ress[i+n]!=-1) continue;
for (int j=0; j<n+m; j++) bio[j]=false;
dfs(1, i+n);
//cout<<i<<":"<<endl;
for (int j=0; j<n; j++)
{
if (!bio[j] && ress[j]==1)
{
q.push(j); //cout<<j<<" ";
}
}
//cout<<endl;
for (int j=0; j<n+m; j++) bio[j]=false;
while (!q.empty())
{
int u=q.front();
q.pop();
for (auto v:guk[u])
{
if (!bio[v]) { bio[v]=true; q.push(v); }
}
}
for (int j=0; j<m; j++) if (ress[j+n]==1 && !bio[j+n]) dal0[i+n]=0;
}
for (int i=0; i<m; i++) if (ress[i+n]==-1) { if (dal0[i+n]) cout<<'?'; else cout<<1; } else cout<<ress[i+n];
//for (int i=0; i<n+m; i++) if (bio[i]) cout<<i<<" ";
//cout<<endl;
/*for (int i=0; i<n+m; i++) if (ress[i]==1) q.push(i);
while (!q.empty())
{
int u=q.front();
q.pop();
for (auto v:g[u])
{
if (v>u) { ress[v]=1; if (!bio[v]) { bio[v]=true; q.push(v); } }
else
{
int veci=-1, ksor=0;
for (auto x:g[u]) { ksor=ksor^x; veci=max(veci, x); }
int w;
if (g[u].size()==3) w=(ksor^veci)^v;
else w=ksor^v;
//{v, w} --(or)--> u
//cout<<v<<" | "<<w<<" ---> "<<u<<endl;
if (ress[w]==0 && !bio[v]) { ress[v]=1; bio[v]=true; q.push(v); }
}
}
}
//for (int i=0; i<n+m; i++) cout<<ress[i]<<" ";
//cout<<endl;
for (int i=0; i<m; i++) if (ress[i+n]==-1) cout<<'?'; else cout<<ress[i+n];*/
return 0;
}
Compilation message
ili.cpp: In function 'int main()':
ili.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i=0; i<s.size(); i++) if (s[i]!='?') { ress[i+n]=s[i]-'0'; if (ress[i+n]==0) q.push(i+n); }
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
