#include <bits/stdc++.h>
using namespace std;
int lg, n, m;
int unde[300001];
struct T
{
int nr1, nr2;
char cmp;
};
T op[300001];
int tata[300001], rang[300001];
int in[300001], in1[300001];
vector <int> v[300001];
bool viz[300001];
int ans[300001];
int find_tata (int nod)
{
int rez = nod;
while (nod != tata[nod])
nod = tata[nod];
while (rez != nod)
{
int cop = tata[rez];
tata[rez] = nod;
rez = cop;
}
return nod;
}
void uneste (int a, int b)
{
if (rang[a] > rang[b])
tata[b] = a;
else
{
tata[a] = b;
if (rang[a] == rang[b])
rang[a]++;
}
}
vector <int> ordine;
bool viz1[300001];
void dfs (int nod)
{
viz1[nod] = 1;
ordine.push_back(nod);
for (auto vecin:v[nod])
if (!viz1[vecin])
dfs(vecin);
}
void solve ()
{
queue <int> q ;
for (int i = 1; i<=n; ++i)
if (in[unde[i]] == 0 && viz[unde[i]] == 0)
{
dfs(unde[i]);
viz[unde[i]] = 1;
}
int current_sum = 1;
for (int i = 1; i<ordine.size(); ++i)
{
if (in1[ordine[i]] == 0)
{
if (current_sum == lg)
for (int j = i - 1, rr = 1; rr <= lg; --j, ++rr)
ans[ordine[j]] = rr;
else
for (int j = i - 1, rr = 1; rr <= current_sum ; --j, ++rr)
ans[ordine[j]] = -1;
current_sum = 1;
}
else
current_sum++;
}
if (current_sum == lg)
for (int j = ordine.size() - 1, rr = 1; rr <= lg ; j--, ++rr)
ans[ordine[j]] = rr;
else
for (int j = ordine.size() - 1, rr = 1; rr <= current_sum; j--, ++rr)
ans[ordine[j]] = -1;
return ;
}
int main ()
{
cin >> lg >> n >> m;
for (int i = 1; i<=m; ++i)
{
int a, b;
char c;
cin >> a >> c >> b;
op[i].nr1 = a;
op[i].nr2 = b;
op[i].cmp = c;
}
for (int i = 1; i<=n; ++i)
tata[i] = i;
for (int i = 1; i<=m; ++i)
if (op[i].cmp == '=')
uneste(find_tata(op[i].nr1), find_tata(op[i].nr2));
for (int i = 1; i<=n; ++i)
unde[i] = find_tata(i);
// use unde[nod] instead of nod
for (int i = 1; i<=m; ++i)
if (op[i].cmp == '<')
{
v[unde[op[i].nr2]].push_back(unde[op[i].nr1]);
in[unde[op[i].nr1]]++;
in1[unde[op[i].nr1]]++;
}
else if (op[i].cmp == '>')
{
v[unde[op[i].nr1]].push_back(unde[op[i].nr2]);
in[unde[op[i].nr2]]++;
in1[unde[op[i].nr2]]++;
}
solve();
for (int i = 1;i<=n;++i)
if (ans[unde[i]] == -1)
cout << "?\n";
else
cout << "K" << ans[unde[i]] << '\n';
return 0;
}
Compilation message
kovanice.cpp: In function 'void solve()':
kovanice.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int i = 1; i<ordine.size(); ++i)
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
93 ms |
16004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
9124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
290 ms |
23980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
