제출 #144943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
144943		LeMur	Ili (COI17_ili)	C++14	0 / 100	3 ms	1144 KiB

ili

////////////////////////////////////////////    _LeMur_
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <chrono>
#include <random>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <ctime>
#include <stack>
#include <queue>
#include <cmath>
#include <list>
#include <map>
#include <set>

using namespace std;

const int N = 10005;
const int inf = 1000 * 1000 * 1000;
const int mod = 998244353;

int n , m;
string s;

bitset <N> mas[N];
bitset <N> A , ids[N];
vector <int> vec;

vector <int> g;
int cnt[N];

vector <int> gr[N];
bool lava[N];

vector <int> M[N] , K[N];
int S[N];

int main(){
	mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
	cin >> n >> m;
    cin >> s;
    for(int i=0;i<m;i++){
        char c1 , c2;
        int x1 , x2;
        bool flag = false;
        cin >> c1 >> x1;
        cin >> c2 >> x2;
        --x1;
        --x2;
        if(c1 == 'x')
            mas[i][x1] = '1';
        else{
            mas[i] |= mas[x1];
            ids[i][x1] = 1;
            ids[i] |= ids[x1];
            if(s[i] == '1' && s[x1] == '1') flag = true;
            if(s[i] == '?' && s[x1] == '1') lava[i] = true;
            if(s[i] == '?' && lava[x1]) lava[i] = true;
        }
        if(c2 == 'x')
            mas[i][x2] = '1';
        else{
            mas[i] |= mas[x2];
            ids[i][x2] = 1;
            ids[i] |= ids[x2];
            if(s[i] == '1' && s[x2] == '1') flag = true;
            if(s[i] == '?' && s[x2] == '1') lava[i] = true;
            if(s[i] == '?' && lava[x2]) lava[i] = true;
        }

        if(s[i] == '0'){
            A |= mas[i];
        }
        if(s[i] == '1' && !flag){
            vec.push_back(i);
        }
    }
    for(int i=0;i<n;i++){
        if(A[i] == 1){
            for(int j=0;j<m;j++){
                mas[j][i] = 0;
            }
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(mas[i][j]){
                M[i].push_back(j);
                K[j].push_back(i);
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<(int)K[i].size();j++){
            int id = K[i][j];
            S[i] += (int)M[id].size();
        }
    }
    for(int j=0;j<m;j++){
        cnt[j] = mas[j].count();
        if(mas[j].count() == 0){
            s[j] = '0';
        }
    }
    for(int i=0;i<m;i++){
        if(s[i] == '?'){
            if(lava[i]){
                s[i] = '1';
                continue;
            }

            int mn = inf;
            int id;

            for(int j=0;j<(int)M[i].size();j++){
                int x = M[i][j];
                if(S[x] < mn){
                    mn = S[x];
                    id = x;
                }
            }

            for(int j=0;j<(int)K[id].size();j++){
                int hamar = K[id][j];
                if(cnt[i] < cnt[hamar])continue;
                bool flag = true;
                for(int h=0;h<(int)M[hamar].size();h++){
                    if(mas[i][ M[hamar][h] ] == 0){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    s[i] = '1';
                    break;
                }
            }
        }
    }
    cout << s << endl;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

ili.cpp: In function 'int main()':
ili.cpp:123:17: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
             int id;
                 ^~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 42
• Subtask 3: 0 / 51