Submission #239591

#TimeUsernameProblemLanguageResultExecution timeMemory
239591MrRobot_28Planinarenje (COCI18_planinarenje)C++17
48 / 160
230 ms20856 KiB
#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()); 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...