oj.uz

Submission #782388

# Submission time Handle Problem Language Result Execution time Memory
782388 2023-07-13T22:58:18 Z MasterTaster Ili (COI17_ili) C++14
49 / 100
 598 ms 2016 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], pombio[MAXN], dal0[MAXN];
vector<int> g[2][MAXN], guk[MAXN];
queue<int> q;

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;

	for (int i=0; i<n+m; i++) ress[i]=-1;
	for (int i=0; i<m; i++) if (s[i]!='?') { ress[i+n]=s[i]-'0';  if (ress[i+n]==0) { q.push(i+n); bio[i+n]=true; } }

	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<<"UU:"<<endl;
		for (auto v:guk[u])
		{
			if (v>u) { cnt[v]++; }
			if (((v<u || cnt[v]>=2 || v<n) && !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+m; j++) pombio[j]=0;
		for (int j=0; j<n; j++)
		{
			if (!bio[j] && ress[j]==1)
			{
				q.push(j); pombio[j]=1;//cout<<j<<" ";
			}
		}
		//cout<<endl;
		for (int j=0; j<n+m; j++) bio[j]=pombio[j];
		
		while (!q.empty())
		{
			int u=q.front();
			q.pop();
			for (auto v:g[0][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;
	}
//cout<<"EE"<<endl;

	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;
}

Subtask #1
7.0 / 7.0

# 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 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct

Subtask #2
42.0 / 42.0

# 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 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 2 ms 980 KB Output is correct
13 Correct 2 ms 980 KB Output is correct
14 Correct 3 ms 980 KB Output is correct

Subtask #3
0 / 51.0

# 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 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 2 ms 980 KB Output is correct
13 Correct 2 ms 980 KB Output is correct
14 Correct 3 ms 980 KB Output is correct
15 Correct 320 ms 1748 KB Output is correct
16 Correct 598 ms 1876 KB Output is correct
17 Correct 404 ms 2016 KB Output is correct
18 Runtime error 2 ms 2004 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -