| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 393106 |
2021-04-22T17:57:39 Z |
asbsfds |
Ili (COI17_ili) |
C++14 |
|
189 ms |
392540 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
392516 KB |
Output is correct |
| 2 |
Correct |
189 ms |
392540 KB |
Output is correct |
| 3 |
Incorrect |
186 ms |
392516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
392516 KB |
Output is correct |
| 2 |
Correct |
189 ms |
392540 KB |
Output is correct |
| 3 |
Incorrect |
186 ms |
392516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
392516 KB |
Output is correct |
| 2 |
Correct |
189 ms |
392540 KB |
Output is correct |
| 3 |
Incorrect |
186 ms |
392516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
