This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
vector <vector <int> > G;
vector <vector <int> > Dp;
void go_to(int v, int p)
{
int flag = 0;
for(int i = 0; i< G[v].size(); i++)
{
int to = G[v][i];
if(to == p)
{
continue;
}
int ind = lower_bound(G[to].begin(), G[to].end(), v) - G[to].begin();
if(Dp[to][ind] == -1)
{
go_to(to, v);
}
if(Dp[to][ind] == 0)
{
flag = 1;
}
}
int ind = lower_bound(G[v].begin(), G[v].end(), p) -G[v].begin();
Dp[v][ind] = flag;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
G.resize(2 * n);
Dp.resize(n * 2);
vector <vector <int> > g(n);
vector <vector <int> > g1(n);
for(int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
a--;
b--;
g[a].push_back(b);
g1[b].push_back(a);
G[a].push_back(b + n);
G[b + n].push_back(a);
}
if(n <= 10)
{
bool dp[(1 << n)][(1 << n)][n][2];
for(int mask1 = (1 << n) - 1; mask1 >= 0; mask1--)
{
for(int mask2 = (1 << n) - 1; mask2 >= 0; mask2--)
{
for(int i = 0; i < n; i++)
{
for(int t = 0; t < 2; t++)
{
if(t == 0)
{
bool flag = false;
for(int a = 0; a < g[i].size(); a++)
{
int to = g[i][a];
if(((1 << to) & mask2) == 0 && !dp[mask1][mask2 | (1 << to)][to][1]){
flag = true;
}
}
dp[mask1][mask2][i][t] = flag;
}
else
{
bool flag = false;
for(int b = 0; b < g1[i].size(); b++)
{
int to = g1[i][b];
if(((1 << to) & mask1) == 0 && !dp[mask1 | (1 << to)][mask2][to][0])
{
flag = true;
}
}
dp[mask1][mask2][i][t] = flag;
}
}
}
}
}
for(int i = 0; i < n; i++)
{
if(dp[(1 << i)][0][i][0])
{
cout << "Slavko\n";
}
else
{
cout << "Mirko\n";
}
}
return 0;
}
for(int i =0; i < n * 2; i++)
{
Dp[i].resize(G[i].size(), -1);
sort(G[i].begin(), G[i].end());
}
for(int i = 0; i < n; i++)
{
int flag = 0;
for(int j = 0; j < G[i].size(); j++)
{
int to = G[i][j];
int ind = lower_bound(G[to].begin(), G[to].end(), i) - G[to].begin();
if(Dp[to][ind] == -1)
{
go_to(to, i);
}
if(Dp[to][ind] == 0)
{
flag = 1;
}
}
if(flag)
{
cout << "Slavko\n";
}
else
{
cout << "Mirko\n";
}
}
return 0;
}
Compilation message (stderr)
planinarenje.cpp: In function 'void go_to(int, int)':
planinarenje.cpp:8:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i< G[v].size(); i++)
~^~~~~~~~~~~~~
planinarenje.cpp: In function 'int main()':
planinarenje.cpp:64:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int a = 0; a < g[i].size(); a++)
~~^~~~~~~~~~~~~
planinarenje.cpp:76:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int b = 0; b < g1[i].size(); b++)
~~^~~~~~~~~~~~~~
planinarenje.cpp:111:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < G[i].size(); j++)
~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |