Submission #55028

#	Time	Username	Problem	Language	Result	Execution time	Memory
55028		ksun48	Arranging Tickets (JOI17_arranging_tickets)	C++14	45 / 100	6073 ms	63896 KiB

arranging_tickets

#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.second;
			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: 10 / 10
• Subtask 2: 35 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15