oj.uz

Submission #245530

# Submission time Handle Problem Language Result Execution time Memory
245530 2020-07-06T16:04:37 Z MatesV13 KOVANICE (COI15_kovanice) C++11
100 / 100
 743 ms 59836 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, 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 21504 KB Output is correct
2 Correct 21 ms 21632 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 29432 KB Output is correct
2 Correct 412 ms 30712 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 23032 KB Output is correct
2 Correct 52 ms 24056 KB Output is correct
3 Correct 53 ms 23928 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 42292 KB Output is correct
2 Correct 635 ms 45684 KB Output is correct
3 Correct 492 ms 45432 KB Output is correct
4 Correct 394 ms 42104 KB Output is correct
5 Correct 623 ms 59836 KB Output is correct