Submission #58628

#	Time	Username	Problem	Language	Result	Execution time	Memory
58628		patrikpavic2	Ili (COI17_ili)	C++17	49 / 100	632 ms	996 KiB

ili

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e4 + 500;

int n, m;
int zn[N], op1[N],op2[N], skup[N], pod[N], perm[N], cnt[N];
char c;

void dfs(int x){
    if(skup[x]) return;
    skup[x] = 1;
    if(x < n) {
        return;
    }
    dfs(op1[x]);
    dfs(op2[x]);
}

bool cmp(const int &A, const int &B){
    return cnt[A] < cnt[B];
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0;i<n;i++) zn[i] = 2;
    for(int i = n;i<n + m;i++){
        scanf(" %c", &c);
        if(c == '?') zn[i] = 2;
        else zn[i] = c - '0';
    }
    for(int i = n;i<n + m;i++){
        char c1, c2;
        scanf(" %c%d %c%d", &c1, &op1[i], &c2, &op2[i]);
        op1[i]--,op2[i]--;
        if(c1 == 'c') op1[i] += n;
        if(c2 == 'c') op2[i] += n;
        if(zn[i] != 0) continue;
        memset(skup, 0 ,sizeof(skup));
        dfs(i);
        for(int j = 0;j<n;j++)
            if(skup[j])
                zn[j] = 0;

    }
    for(int i = n;i<n + m;i++){
        memset(skup, 0 ,sizeof(skup));
        dfs(i);
        for(int j = 0;j<n;j++) if(skup[j] && zn[j]) cnt[i]++;
        if(zn[i] != 2) continue;
        zn[i] = 0;
        for(int j = 0;j<n;j++){
            if(skup[j] && zn[j] != 0)
                zn[i] = 2;
        }
    }
    for(int i = 0;i<m;i++) perm[i] = n + i;
    sort(perm, perm + m, cmp);
    for(int l = 0;l<m;l++){
        int i = perm[l];
        if(zn[i] != 2) continue;
        memset(skup, 0, sizeof(skup));
        memset(pod, 0, sizeof(pod));
        dfs(i);
        for(int i = 0;i<n;i++)
            if(skup[i] || !zn[i]) pod[i] = 1;
        for(int j = n;j<n + m;j++){
            if(pod[op1[j]] && pod[op2[j]])
                pod[j] = 1;
        }
        for(int j = n;j<n + m;j++){
            if(pod[j] && zn[j] == 1) zn[i] = 1;
        }
    }
    for(int i = n;i<n + m;i++){
        if(zn[i] == 2)printf("?");
        else printf("%c", '0' + zn[i]);
    }
}

Compilation message (stderr)

ili.cpp: In function 'int main()':
ili.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
ili.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &c);
         ~~~~~^~~~~~~~~~~
ili.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c%d %c%d", &c1, &op1[i], &c2, &op2[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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