oj.uz

Submission #239592

# Submission time Handle Problem Language Result Execution time Memory
239592 2020-06-16T14:00:40 Z MrRobot_28 Planinarenje (COCI18_planinarenje) C++17
80 / 160
 230 ms 262148 KB 
#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

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++)
                  ~~^~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 20856 KB Output is correct
2 Correct 197 ms 20856 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 20856 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1792 KB Output is correct
2 Correct 9 ms 1920 KB Output is correct
3 Correct 8 ms 1792 KB Output is correct
4 Correct 9 ms 1920 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 175 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 187 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 173 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 172 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -