Submission #1278336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278336		mhn_neek	Arranging Tickets (JOI17_arranging_tickets)	C++20	0 / 100	3 ms	572 KiB

arranging_tickets

//In the name of God
#include<bits/stdc++.h>
/*MHN*/
using namespace std;
typedef long long int lli;
typedef long double ld;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=4e5+100;
const lli mod=1e9+7;//998244353;//1e9+9
const lli INF=1e18;
lli power(lli x,lli y){lli res = 1;x = x % mod;while(y>0){if( y & 1 ){res = (res * x) % mod;}y = y >> 1;x = (x * x)%mod;}return res;}
lli modinv(lli x){return power(x,mod-2);}
lli divide(lli x,lli y){return ((x%mod) * modinv(y))%mod;}
#define all(v) v.begin(),v.end()
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define SUM(v) accumulate(v.begin(),v.end(), 0LL)
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define TEST int TQPWIEJR; cin>>TQPWIEJR;while(TQPWIEJR--)
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define sep " "
lli tmp;
lli n,m;
vp E;
ve adj[N];
bool vis[N];
lli ps[N];
lli L;
lli get_dis(lli r){
	lli l =L;
	if(l > r){
		return n-l + r;
	}
	return r-l;
}



lli solve(lli in){
	multiset<lli> S;
	lli ans = 0;
	for(lli i = in;; i = (i < n ? i+1 : 1)){
		L = i;
		vis[i] = 1;
		while(S.find(i)!=S.end())S.erase(S.find(i));
		ps[i] += ps[(i == 1 ? n : i-1)];
		ve ca;
		for(auto j : adj[i]){
			if(vis[j] == 0){
				ca.PB(j);
				ps[i] += 1;
				ps[j] -= 1;
			}
		}

		sort(all(ca),[](lli x,lli y){
			return get_dis(x) < get_dis(y);		
		});
		
		lli p = 0;
		while(p < (lli)ca.size() && (lli)S.size()*2 < ps[i]-1){
			S.insert(ca[p++]);
		}
		ans += ca.size() - p;

		if(i == (in == 1 ? n :  in-1))break;
	}
	FORS(i,n)vis[i] = 0,ps[i]= 0;
	return ans;
}


int main(){
    migmig;
	cin>>n>>m;
	FOR(i,m){
		lli a,b,c;
		cin>>a>>b>>c;
		E.PB(MP(a,b));
		adj[a].PB(b);
		adj[b].PB(a);
	}
	lli ans = INF;
	FORS(i,n){
		ans = min(ans,solve(i));
	}
	cout<<ans<<endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15