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
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/*
 *  Copyright (C) 2015  Paweł Widera
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details:
 *  http://www.gnu.org/licenses/gpl.html
 */
#include <vector>
#include <deque>
#include <unordered_set>
#include <tuple>
#include <algorithm>
#include <iostream>
using namespace std;


// breadth-first search -  checks if a path from source to target exists
// and fills the vector of distances from source
bool is_path(int source, int target, vector<vector<int>>& neighbours,
	vector<vector<int>>& capacity, vector<int>& distance) {

	for (unsigned int i=0; i < distance.size(); ++i) {
		distance[i] = -999;
	}

	deque<int> queue;
	queue.push_back(source);
	distance[source] = 0;

	while (!queue.empty()) {
		int current = queue.front();
		queue.pop_front();

		for (auto node: neighbours[current]) {
			if (distance[node] < 0 && capacity[current][node] > 0) {
				distance[node] = distance[current] + 1;
				queue.push_back(node);
			}
		}
	}

	if (distance[target] < 0) {
		return false;
	}
	return true;
}


// depth first search - finds a flow increasing path
int dfs(int current, int target, int min_capacity, vector<vector<int>>& neighbours,
	vector<vector<int>>& capacity, vector<int>& distance, vector<unsigned int>& first) {

	if (current == target || min_capacity == 0) {
		return min_capacity;
	}

	int total_flow = 0;
	for (unsigned int& i = first[current]; i < neighbours[current].size(); ++i) {
		int next = neighbours[current][i];

		// use only distance increasing edges of non-zero capacity
		if (distance[next] == distance[current] + 1 && capacity[current][next] > 0) {

			// continue path from next and find its max flow
			int flow = dfs(next, target, min(min_capacity, capacity[current][next]),
				neighbours, capacity, distance, first);

			// move the capacity of used edges to the reversed edges
			capacity[current][next] -= flow;
			capacity[next][current] += flow;
			min_capacity -= flow;
			total_flow += flow;

			if (min_capacity == 0) {
				break;
			}
		}
	}
	return total_flow;
}


// adds graph edge (two directional) and its weight (capacity)
void add_edge(int a, int b, int weight, vector<vector<int>>& neighbours,
	vector<vector<int>>& capacity) {

	capacity[a][b] = weight;
	neighbours[a].push_back(b);
	neighbours[b].push_back(a);
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	vector<tuple<int, int, int>> tasks;
	tasks.reserve(n);

	unordered_set<int> timepoints;

	int start, stop, duration;
	int total_duration = 0;

	for (int i = 0; i < n; ++i) {
		cin >> start >> stop >> duration;
		tasks.push_back(make_tuple(start, stop, duration));
		total_duration += duration;
		timepoints.insert(start);
		timepoints.insert(stop);
	}

	// sort the time points
	vector<int> points(begin(timepoints), end(timepoints));
	sort(begin(points), end(points));

	int nodes = points.size() + n + 1;

	vector<vector<int>> neighbours(nodes);
	vector<int> distance(nodes, -999);
	vector<vector<int>> capacity(nodes, vector<int>(nodes, 0));

	int max_capacity = 0;

	// add edges from source node
	for (int i = 1; i < (int)points.size(); ++i) {
		int weight = m * (points[i] - points[i - 1]);
		max_capacity = max(weight, max_capacity);
		add_edge(0, i, weight, neighbours, capacity);
	}
	// add edges to target node
	for (int i = 0; i < n; ++i) {
		int weight = get<2>(tasks[i]);
		max_capacity = max(weight, max_capacity);
		add_edge(points.size() + i, nodes - 1, weight, neighbours, capacity);
	}
	// add inner edges
	for (int i = 1; i < (int)points.size(); ++i) {
		for (int j = 0; j < n; ++j) {
			// points are between ready time and deadline
			if (points[i - 1] >= get<0>(tasks[j]) && points[i] <= get<1>(tasks[j])) {
				int weight = (points[i] - points[i - 1]);
				max_capacity = max(weight, max_capacity);
				add_edge(i, points.size() + j, weight, neighbours, capacity);
			}
		}
	}

	int max_flow = 0;
	while (is_path(0, nodes - 1, neighbours, capacity, distance)) {
		vector<unsigned int> first(nodes, 0);
		max_flow += dfs(0, nodes - 1, max_capacity, neighbours, capacity, distance, first);
	}

	string answer = "NIE";
	if (max_flow == total_duration) {
		answer = "TAK";
	}
	cout << answer << endl;

	return 0;
}