oj.uz

Submission #545626

# Submission time Handle Problem Language Result Execution time Memory
545626 2022-04-05T02:10:38 Z Monarchuwu Ili (COI17_ili) C++17
0 / 100
 1 ms 340 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 = n + 1; i <= n + 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -