oj.uz

Submission #545627

# Submission time Handle Problem Language Result Execution time Memory
545627 2022-04-05T02:13:39 Z Monarchuwu Ili (COI17_ili) C++17
49 / 100
 335 ms 2544 KB 
/**
 *  Problem:    COI17_ili (Croatian Olympiad in Informatics 2017)
 *  Link:       https://oj.uz/problem/view/COI17_ili
**/
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 1e4 + 7;
int n, m;
char c[N];
map<string, int> mp;
int g[N][2];

int dp[N << 1];
void gogo(bool f = false) {
    fill(dp + 1, dp + n + 1, f ? 1 : -1);
    for (int i = 1; i <= m; ++i)
        dp[n + i] = c[i] == '?' ? -1 : c[i] - '0';

    for (int i = m + n; i > n; --i)
        if (!dp[i]) dp[g[i][0]] = dp[g[i][1]] = 0;
    for (int i = n + 1; i <= m + n; ++i) if (f || !~dp[i]) {
        if (dp[g[i][0]] == 1 || dp[g[i][1]] == 1) dp[i] = 1;
        else if (!dp[g[i][0]] && !dp[g[i][1]]) dp[i] = 0;
    }
}
void prep() {
    gogo();
    for (int i = 1; i <= m; ++i)
        c[i] = "?01"[dp[i + n] + 1];
}
void solve() {
    for (int i = 1; i <= m; ++i) if (c[i] == '?') {
        c[i] = '0'; // if c[i] == '0'
        gogo(true);

        bool f(true);
        for (int j = 1; j <= m; ++j)
            if (c[j] != '?' && dp[j + n] != c[j] - '0') {
                f = false;
                break;
            }
        c[i] = "1?"[f];
    }
    cout << (c + 1) << '\n';
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m >> (c + 1);
    for (int i = 1; i <= n; ++i) mp["x" + to_string(i)] = mp.size() + 1;
    for (int i = 1; i <= m; ++i) mp["c" + to_string(i)] = mp.size() + 1;
    for (int i = 1; i <= m; ++i) {
        string s1, s2; cin >> s1 >> s2;
        g[i + n][0] = mp[s1], g[i + n][1] = mp[s2];
    }
    prep();
    solve();
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 340 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 31 ms 980 KB Output is correct
16 Correct 335 ms 1160 KB Output is correct
17 Correct 267 ms 1164 KB Output is correct
18 Runtime error 12 ms 2544 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -