Submission #245527

# Submission time Handle Problem Language Result Execution time Memory
245527 2020-07-06T15:37:46 Z MatesV13 KOVANICE (COI15_kovanice) C++11
0 / 100
326 ms 43760 KB
#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){
	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++)
		check(y[i]);
	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; 
	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++) visited[i]=0;
for (int i=1; i<=m; i++) if (val[i]==1) check(i);	
for (int i=1; i<=m; i++){
	if (moguce[i]) cout << "K" << val[i] << endl;
	else cout << "?\n";
}
return 0;
}

Compilation message

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)':
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: In function 'void solve(int)':
kovanice.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<x.size(); i++)
                ~^~~~~~~~~
kovanice.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<veci[x[i]].size(); j++)
                 ~^~~~~~~~~~~~~~~~~~
kovanice.cpp:34:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<y.size(); i++)
                ~^~~~~~~~~
kovanice.cpp:36:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<y.size(); i++)
                ~^~~~~~~~~
kovanice.cpp:39: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<x.size(); i++)
                ~^~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:53:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++){
                ~^~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 21504 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 268 ms 30688 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 23544 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 326 ms 43760 KB Output isn't correct
2 Halted 0 ms 0 KB -