Submission #782390

#	Time	Username	Problem	Language	Result	Execution time	Memory
782390		MasterTaster	Ili (COI17_ili)	C++14	100 / 100	2075 ms	3260 KiB

ili

#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 20010

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 / 7
• Subtask 2: 42 / 42
• Subtask 3: 51 / 51