oj.uz

Submission #55027

# Submission time Handle Problem Language Result Execution time Memory
55027 2018-07-05T21:03:55 Z ksun48 Arranging Tickets (JOI17_arranging_tickets) C++14
0 / 100
 3 ms 684 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL two(vector<vector<LL> > z, LL n){
	LL maxcross = 0;
	LL numcross[n][n];

	vector<LL> ends(n, 0);
	vector<LL> backs[n];
	for(int j = 0; j < z.size(); j++){
		int c = z[j][0];
		int d = z[j][1];
		ends[c]++;
		ends[d]++;
		backs[d].push_back(c);
	}
	for(int a = 0; a < n; a++){
		LL f = 0;
		for(int b = a+1; b < n; b++){
			f += ends[b];
			for(int r : backs[b]){
				if(r >= a+1){
					f -= 2;
				}
			}
			numcross[a][b] = f;
			maxcross = max(maxcross, numcross[a][b]);
		}
	}

	vector<pair<LL,LL> > pairs;
	for(int a = 0; a < n; a++){
		LL f = 0;
		for(int b = a+1; b < n; b++){
			if(numcross[a][b] == maxcross){
				pairs.push_back({a,b});
			}
		}
	}
	LL realbound = (maxcross + 1) / 2;
	if(maxcross % 2 == 1) return realbound;
	for(auto p1 : pairs){
		for(auto p2 : pairs){
			int a = p1.first;
			int c = p1.second;
			int b = p2.first;
			int d = p2.first;
			if(a >= b || b >= c || c >= d) continue;
			if(numcross[a][b] % 2 == 1){
				return realbound + 1;
			}
		}
	}
	return realbound;
}

int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	LL n, m;
	cin >> n >> m;
	// stations 1 to n
	vector<vector<LL> > z;
	for(int i = 0; i < m; i++){
		LL a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		if(a > b) swap(a,b);
		for(int j = 0; j < c; j++){
			z.push_back(vector<LL>({a,b}));
		}
	}
	LL bound = two(z, n);
	cout << bound << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 3 ms 684 KB Output is correct
9 Correct 3 ms 684 KB Output is correct
10 Correct 2 ms 684 KB Output is correct
11 Correct 2 ms 684 KB Output is correct
12 Correct 3 ms 684 KB Output is correct
13 Incorrect 2 ms 684 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 3 ms 684 KB Output is correct
9 Correct 3 ms 684 KB Output is correct
10 Correct 2 ms 684 KB Output is correct
11 Correct 2 ms 684 KB Output is correct
12 Correct 3 ms 684 KB Output is correct
13 Incorrect 2 ms 684 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 3 ms 684 KB Output is correct
9 Correct 3 ms 684 KB Output is correct
10 Correct 2 ms 684 KB Output is correct
11 Correct 2 ms 684 KB Output is correct
12 Correct 3 ms 684 KB Output is correct
13 Incorrect 2 ms 684 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 3 ms 684 KB Output is correct
9 Correct 3 ms 684 KB Output is correct
10 Correct 2 ms 684 KB Output is correct
11 Correct 2 ms 684 KB Output is correct
12 Correct 3 ms 684 KB Output is correct
13 Incorrect 2 ms 684 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 3 ms 684 KB Output is correct
9 Correct 3 ms 684 KB Output is correct
10 Correct 2 ms 684 KB Output is correct
11 Correct 2 ms 684 KB Output is correct
12 Correct 3 ms 684 KB Output is correct
13 Incorrect 2 ms 684 KB Output isn't correct
14 Halted 0 ms 0 KB -