oj.uz

Submission #126545

# Submission time Handle Problem Language Result Execution time Memory
126545 2019-07-08T04:13:44 Z briansu Arranging Tickets (JOI17_arranging_tickets) C++14
10 / 100
 332 ms 504 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define REP(i, n) for(int i = 0;i < n;i ++)
#define REP1(i, n) for(int i = 1;i <= n;i ++)
#define FILL(i, n) memset(i, n, sizeof(i))
#define X first
#define Y second
#define pb push_back
#define SZ(_a) ((int)(_a).size())
#define ALL(_a) (_a).begin(), (_a).end()
#ifdef brian
#define IOS() 
template<typename T>void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...t>void _do(T &&x, t &&...X){cerr<<x<<", ";_do(X...);}
#define debug(...) {\
	fprintf(stderr, "%s - %d (%s) = ", __PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__);\
	_do(__VA_ARGS__);\
}
#else
#define debug(...)
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#endif

const ll MAXn = 1e5 + 5;
const ll INF = ll(1e18);
const ll MOD = 1000000007;

ll a[MAXn], b[MAXn], c[MAXn];

ll fg[MAXn], mn[MAXn];

map<ii, ll> mp;
vector<ii> dt;
ll n, m;

ll d[MAXn];

ll chk(ll x)
{
	REP1(i, n)d[i] = 0;
	for(int i = 0, I = 1;i < SZ(dt);i ++, I<<=1)
	{
		if(I & x)for(int j = dt[i].X;j < dt[i].Y;j ++)d[j]++;
		else
		{
			for(int j = 1;j < dt[i].X;j ++)d[j] ++;
			for(int j = dt[i].Y;j <= n;j ++)d[j] ++;
		}
	}
	ll mx = 0;
	REP1(i, n)mx = max(mx, d[i]);
	return mx;
}

int main(){
	IOS();
	cin>>n>>m;
	REP1(i, m)cin>>a[i]>>b[i]>>c[i];
	REP1(i, m)if(a[i] > b[i])swap(a[i], b[i]);
	REP1(i, m)mp[ii(a[i], b[i])]++;
	ll tmptt = 0;
	for(auto &p:mp)
	{
		tmptt += p.Y / 2;
		if(p.Y & 1)dt.pb(p.X);
	}
	ll ans = INF;
	REP(I, (1<<SZ(dt)))ans = min(ans, chk(I));
	cout<<ans + tmptt<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 376 KB Output is correct
2 Correct 75 ms 376 KB Output is correct
3 Correct 19 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 18 ms 376 KB Output is correct
6 Correct 76 ms 376 KB Output is correct
7 Correct 20 ms 376 KB Output is correct
8 Correct 19 ms 376 KB Output is correct
9 Correct 321 ms 416 KB Output is correct
10 Correct 19 ms 504 KB Output is correct
11 Correct 77 ms 376 KB Output is correct
12 Correct 332 ms 504 KB Output is correct
13 Correct 76 ms 376 KB Output is correct
14 Correct 74 ms 412 KB Output is correct
15 Correct 74 ms 504 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 376 KB Output is correct
2 Correct 75 ms 376 KB Output is correct
3 Correct 19 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 18 ms 376 KB Output is correct
6 Correct 76 ms 376 KB Output is correct
7 Correct 20 ms 376 KB Output is correct
8 Correct 19 ms 376 KB Output is correct
9 Correct 321 ms 416 KB Output is correct
10 Correct 19 ms 504 KB Output is correct
11 Correct 77 ms 376 KB Output is correct
12 Correct 332 ms 504 KB Output is correct
13 Correct 76 ms 376 KB Output is correct
14 Correct 74 ms 412 KB Output is correct
15 Correct 74 ms 504 KB Output is correct
16 Incorrect 5 ms 376 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 376 KB Output is correct
2 Correct 75 ms 376 KB Output is correct
3 Correct 19 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 18 ms 376 KB Output is correct
6 Correct 76 ms 376 KB Output is correct
7 Correct 20 ms 376 KB Output is correct
8 Correct 19 ms 376 KB Output is correct
9 Correct 321 ms 416 KB Output is correct
10 Correct 19 ms 504 KB Output is correct
11 Correct 77 ms 376 KB Output is correct
12 Correct 332 ms 504 KB Output is correct
13 Correct 76 ms 376 KB Output is correct
14 Correct 74 ms 412 KB Output is correct
15 Correct 74 ms 504 KB Output is correct
16 Incorrect 5 ms 376 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 376 KB Output is correct
2 Correct 75 ms 376 KB Output is correct
3 Correct 19 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 18 ms 376 KB Output is correct
6 Correct 76 ms 376 KB Output is correct
7 Correct 20 ms 376 KB Output is correct
8 Correct 19 ms 376 KB Output is correct
9 Correct 321 ms 416 KB Output is correct
10 Correct 19 ms 504 KB Output is correct
11 Correct 77 ms 376 KB Output is correct
12 Correct 332 ms 504 KB Output is correct
13 Correct 76 ms 376 KB Output is correct
14 Correct 74 ms 412 KB Output is correct
15 Correct 74 ms 504 KB Output is correct
16 Incorrect 5 ms 376 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 376 KB Output is correct
2 Correct 75 ms 376 KB Output is correct
3 Correct 19 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 18 ms 376 KB Output is correct
6 Correct 76 ms 376 KB Output is correct
7 Correct 20 ms 376 KB Output is correct
8 Correct 19 ms 376 KB Output is correct
9 Correct 321 ms 416 KB Output is correct
10 Correct 19 ms 504 KB Output is correct
11 Correct 77 ms 376 KB Output is correct
12 Correct 332 ms 504 KB Output is correct
13 Correct 76 ms 376 KB Output is correct
14 Correct 74 ms 412 KB Output is correct
15 Correct 74 ms 504 KB Output is correct
16 Incorrect 5 ms 376 KB Output isn't correct
17 Halted 0 ms 0 KB -