#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++){
~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
24 ms |
21504 KB |
Output is correct |
| 2 |
Correct |
21 ms |
21632 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
387 ms |
29432 KB |
Output is correct |
| 2 |
Correct |
412 ms |
30712 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
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 |
| # |
결과 |
실행 시간 |
메모리 |
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 |
