Submission #245530

#	Time	Username	Problem	Language	Result	Execution time	Memory
245530		MatesV13	KOVANICE (COI15_kovanice)	C++11	100 / 100	743 ms	59836 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
long long n, m, v; long long val[300005]; int moguce[300005];
vector<int> manji[300005], veci[300005], eq[300005];
bool visited[300005];
void dfs(int idx, vector<int> &ime){
	if (visited[idx]) return;
	visited[idx]=1; ime.push_back(idx);
	for (int i=0; i<eq[idx].size(); i++)
		dfs(eq[idx][i], ime);
	return;
}
void check(int idx, int value){
	if (moguce[idx]) return;
	vector<int> x; dfs(idx, x);
	for (int i=0; i<x.size(); i++)
		moguce[x[i]]=1; 
	vector<int> y;
	for (int i=0; i<x.size(); i++)
		for (int j=0; j<veci[x[i]].size(); j++)
			dfs(veci[x[i]][j], y);
	for (int i=0; i<y.size(); i++)
		visited[y[i]]=0;
	for (int i=0; i<y.size(); i++)
		if (val[y[i]]==value) check(y[i], value+1);
	for (int i=0; i<x.size(); i++)
		visited[x[i]]=0;
	return;
} 
void solve(int idx){
	if (val[idx]) return;
	vector<int> x; dfs(idx, x); vector<int> y;
	for (int i=0; i<x.size(); i++)
		for (int j=0; j<veci[x[i]].size(); j++)
			dfs(veci[x[i]][j], y);
	for (int i=0; i<y.size(); i++)
		visited[y[i]]=0;
	for (int i=0; i<y.size(); i++)
		solve(y[i]);
	long long minn=n+1;
	for (int i=0; i<y.size(); i++)
		minn=min(minn, val[y[i]]);
	for (int i=0; i<x.size(); i++)
		val[x[i]]=minn-1; 
	for (int i=0; i<x.size(); i++)
		visited[x[i]]=0;
	return;
}
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> v;
while (v--){
	string s; cin >> s;
	int prvibr=0, drugibr=0;
	char oper='0';
	for (int i=0; i<s.size(); i++){
		if (s[i]>='0' and s[i]<='9'){
			if (oper=='0') prvibr=prvibr*10+s[i]-'0';
			else drugibr=drugibr*10+s[i]-'0';
		} else oper=s[i];
	}
	if (oper=='='){
		eq[prvibr].push_back(drugibr);
		eq[drugibr].push_back(prvibr);
	}
	else {
		veci[prvibr].push_back(drugibr);
		manji[drugibr].push_back(prvibr);
	}
}
for (int i=1; i<=m; i++) 
	solve(i);
for (int i=1; i<=m; i++) 
	if (val[i]==1) check(i, 2);	
for (int i=1; i<=m; i++){
	if (moguce[i]) cout << "K" << val[i] << endl;
	else cout << "?\n";
}
return 0;
}

Compilation message (stderr)

kovanice.cpp: In function 'void dfs(int, std::vector<int>&)':
kovanice.cpp:9:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<eq[idx].size(); i++)
                ~^~~~~~~~~~~~~~~
kovanice.cpp: In function 'void check(int, int)':
kovanice.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<x.size(); i++)
                ~^~~~~~~~~
kovanice.cpp:19:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<x.size(); i++)
                ~^~~~~~~~~
kovanice.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<veci[x[i]].size(); j++)
                 ~^~~~~~~~~~~~~~~~~~
kovanice.cpp:22:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<y.size(); i++)
                ~^~~~~~~~~
kovanice.cpp:24:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<y.size(); i++)
                ~^~~~~~~~~
kovanice.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<x.size(); i++)
                ~^~~~~~~~~
kovanice.cpp: In function 'void solve(int)':
kovanice.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<x.size(); i++)
                ~^~~~~~~~~
kovanice.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<veci[x[i]].size(); j++)
                 ~^~~~~~~~~~~~~~~~~~
kovanice.cpp:36:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<y.size(); i++)
                ~^~~~~~~~~
kovanice.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<y.size(); i++)
                ~^~~~~~~~~
kovanice.cpp:41:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<y.size(); i++)
                ~^~~~~~~~~
kovanice.cpp:43:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<x.size(); i++)
                ~^~~~~~~~~
kovanice.cpp:45:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<x.size(); i++)
                ~^~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:57:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++){
                ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40