#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);
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, 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: 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 |
20 ms |
21632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
271 ms |
29444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
22784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
334 ms |
39800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
