Submission #393106

#TimeUsernameProblemLanguageResultExecution timeMemory
393106asbsfdsIli (COI17_ili)C++14
0 / 100
189 ms392540 KiB
#include <bits/stdc++.h> #define X first #define Y second using namespace std; typedef long long llint; const int maxn = 2e4+10; const int base = 31337; const int mod = 1e9+7; const int inf = 0x3f3f3f3f; const int logo = 20; const int off = 1 << logo; const int treesiz = off << 1; int n, m; bool dp[maxn][maxn]; vector< int > graph[maxn]; char out[maxn]; int get() { string s; cin >> s; char type = s[0]; int x = 0; for (int i = 1; i < s.size(); i++) { x *= 10; x += s[i] - '0'; } x--; if (type == 'c') x += n; return x; } void dfs(int x) { out[x] = '0'; for (int i = 0; i < graph[x].size(); i++) { int tren = graph[x][i]; dfs(tren); } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; memset(out, '?', sizeof out); for (int i = 0; i < m; i++) { cin >> out[i + n]; } for (int i = 0; i < m; i++) { graph[i + n].push_back(get()); graph[i + n].push_back(get()); } for (int i = n; i < m + n; i++) { if (out[i] == '0') { dfs(i); } } for (int i = n; i < m + n; i++) { bool flag = true; for (int j = 0; j < graph[i].size(); j++) { int tren = graph[i][j]; if (out[tren] != '0') flag = false; } if (flag) out[i] = '0'; } memset(dp, false, sizeof dp); for (int i = 0; i < n; i++) if (out[i] != '0') dp[i][i] = true; for (int i = n; i < m + n; i++) { for (int j = 0; j < graph[i].size(); j++) { int tren = graph[i][j]; for (int l = 0; l < n; l++) { if (dp[tren][l]) dp[i][l] = true; } } } for (int i = n; i < m + n; i++) { for (int j = n; j < i; j++) { bool flag = true; for (int l = 0; l < n; l++) { if (dp[j][l] && !dp[i][l]) flag = false; } if (flag) dp[i][j] = true; } } for (int i = 0; i < m + n; i++) { if (out[i] != '1') continue; for (int j = i + 1; j < m + n; j++) { if (dp[j][i]) out[j] = '1'; } } /** for (int i = 0; i < n + m; i++) { for (int j = 0; j < n + m; j++) printf("%d", dp[i][j]); printf("\n"); } printf("debug: "); for (int i = 0; i < n + m; i++) printf("%c", out[i]); printf("\n"); **/ for (int i = n; i < n + m; i++) cout << out[i]; return 0; }

Compilation message (stderr)

ili.cpp: In function 'int get()':
ili.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for (int i = 1; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~
ili.cpp: In function 'void dfs(int)':
ili.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 0; i < graph[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
ili.cpp: In function 'int main()':
ili.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int j = 0; j < graph[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
ili.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for (int j = 0; j < graph[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...