USACO/CowntactTracing.java at main · nuhan2007/USACO · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//2020 US Open Bronze Problem 3
import java.util.*;
import java.io.*;
public class CowntactTracing {

    static boolean[] cowEndsInfected;
    static int n, t, maxN, maxT;
    static int[] cowX;
    static int[] cowY;

    static boolean consistentWithData(int patientZero, int k) {
        boolean[] infectedCows = new boolean[maxN+1];
        Arrays.fill(infectedCows, false);
        infectedCows[patientZero] = true;
        int[] numHandShakes = new int[maxN+1];
        for(int i=0; i<=maxT; i++) {
            int c1 = cowX[i];
            int c2 = cowY[i];

            if(infectedCows[c1]) numHandShakes[c1]++;
            if(infectedCows[c2]) numHandShakes[c2]++;
            if(numHandShakes[c1] <= k && infectedCows[c1]) infectedCows[c2] = true;
            if(numHandShakes[c2] <= k && infectedCows[c2]) infectedCows[c1] = true;
        }

        for(int j=1; j<=n; j++) {
            if(infectedCows[j] != cowEndsInfected[j]) return false;
        }
        return true;
    }
    public static void main(String[] args) throws IOException{
        maxN = 100;
        maxT = 250;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());
        String s = br.readLine();
        cowEndsInfected = new boolean[n+1];
        for(int i=1; i<=n; i++) {
            if(s.charAt(i-1) == '1') cowEndsInfected[i] = true;
            else cowEndsInfected[i] = false;
        }
        cowX = new int[maxT+1];
        cowY = new int[maxT+1];
        for(int i=0; i<t; i++) {
            st = new StringTokenizer(br.readLine());
            int tt = Integer.parseInt(st.nextToken());
            cowX[tt] = Integer.parseInt(st.nextToken());
            cowY[tt] = Integer.parseInt(st.nextToken());
        }

        boolean[] possibleI = new boolean[maxN+1];
        boolean[] possibleK = new boolean[maxT+2];
        for(int i=1; i<=n; i++) {
            for(int k=0; k<maxT; k++) {
                if(consistentWithData(i, k));
                possibleI[i] = true;
                possibleK[k] = true;
            }
        }

        int numPatientZero = 0;
        int lowerK = Integer.MAX_VALUE;
        int upperK = Integer.MIN_VALUE;

        for(int i=0; i<maxN; i++) {
            if(possibleI[i]) numPatientZero++;
        }
        for(int k=0; k<=maxT; k++) {
            if(possibleK[k]) {
                lowerK = k;
                break;
            }
        }
        for(int k=maxT+1; k>=0; k--) {
            if(possibleK[k]) {
                upperK = k;
                break;
            }
        }

        System.out.print(numPatientZero + " " + lowerK + " ");
        if(upperK == maxT+1) System.out.print("Infinity");
        else System.out.print(upperK);

    }
}