#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl
struct node {
int val;
vector<int> a,y,e;
int deg = 0;
};
vector<node> nodes;
vector<int> res;
queue<int> q;
map<int,int> seen;
int bfs(int x,int n) {
q.push(x);
int mxd = -1, mind = 1e9;
vector<int> visited;
while (q.size()) {
auto f = q.front();
mxd = max(mxd,nodes[f].deg);
mind = min(mind,nodes[f].deg);
visited.push_back(f);
if (seen[f]) {
q.pop();continue;
}seen[f]=1;
for (int i = 0;i<nodes[f].y.size();i++) {
nodes[nodes[f].y[i]].deg=nodes[f].deg+1;
q.push(nodes[f].y[i]);
}
for (int i = 0;i<nodes[f].a.size();i++) {
nodes[nodes[f].a[i]].deg=nodes[f].deg-1;
q.push(nodes[f].a[i]);
}
for (int i = 0;i<nodes[f].e.size();i++) {
nodes[nodes[f].e[i]].deg=nodes[f].deg;
q.push(nodes[f].e[i]);
}
}
if (mxd-mind != n-1) return 0;
for (int i = 0;i<visited.size();i++) {
res[visited[i]] = nodes[visited[i]].deg+1-mind;
}
return 0;
}
int32_t main() {
int n,m,v;cin>>n>>m>>v;
nodes = vector<node>(m+1);
res = vi(m+1,-1);
for (int i = 0;i<m;i++) {
int a,c;char b;cin>>a>>b>>c;
if (b=='='){
nodes[a].e.push_back(c);
nodes[c].e.push_back(a);
} else {
nodes[a].y.push_back(c);
nodes[c].a.push_back(a);
}
}
for (int i = 0;i<m;i++) {
if (seen[i+1]) continue;
bfs(i+1,n);
}
for (int i = 1;i<res.size();i++) {
if (res[i]!=-1) cout<<"K"<<res[i]<<endl;
else cout<<"K?"<<endl;
}
return 0;
}
Compilation message
kovanice.cpp: In function 'int bfs(int, int)':
kovanice.cpp:37:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 0;i<nodes[f].y.size();i++) {
| ~^~~~~~~~~~~~~~~~~~
kovanice.cpp:41:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int i = 0;i<nodes[f].a.size();i++) {
| ~^~~~~~~~~~~~~~~~~~
kovanice.cpp:45:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int i = 0;i<nodes[f].e.size();i++) {
| ~^~~~~~~~~~~~~~~~~~
kovanice.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int i = 0;i<visited.size();i++) {
| ~^~~~~~~~~~~~~~~
kovanice.cpp: In function 'int32_t main()':
kovanice.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i = 1;i<res.size();i++) {
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
441 ms |
34140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
897 ms |
57032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
