제출 #545627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545627		Monarchuwu	Ili (COI17_ili)	C++17	49 / 100	335 ms	2544 KiB

ili

/**
 *  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 / 7
• Subtask 2: 42 / 42
• Subtask 3: 0 / 51