Submission #55029

#	Time	Username	Problem	Language	Result	Execution time	Memory
55029		ksun48	Arranging Tickets (JOI17_arranging_tickets)	C++14	65 / 100	232 ms	178988 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++){
		numcross[a][a] = 0;
		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[2];
	for(int a = 0; a < n; a++){
		LL f = 0;
		for(int b = a+1; b < n; b++){
			if(numcross[a][b] == maxcross){
				pairs[numcross[0][a] % 2].push_back({a,b});
			}
		}
	}
	LL realbound = (maxcross + 1) / 2;
	if(maxcross % 2 == 1) return realbound;
	for(int r = 0; r < 2; r++){
		for(auto p1 : pairs[r]){
			for(auto p2 : pairs[1-r	]){
				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: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15