結果

問題 No.596 郵便配達
ユーザー Guowen Rong
提出日時 2025-05-17 17:04:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,348 bytes
コンパイル時間 2,489 ms
コンパイル使用メモリ 197,808 KB
実行使用メモリ 62,224 KB
最終ジャッジ日時 2025-05-17 17:05:03
合計ジャッジ時間 6,302 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define lowbit(x) x & (-x)
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define ctz(x) __builtin_ctz(x)
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 7e6 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
int n, m;
inline void ckmin(int &x, int y){
	if(y < x)
	  x = y;
}
inline void ckmax(int &x, int y){
	if(y > x)
	  x = y;
}
int f(vector<int> const & v) {
	int n = (int)v.size();
	vector<int> d(n - 1), sl(n), sr(n);
	for(int i = 0; i < n - 1; ++i)
	  if((i + 1) & 1)
	    d[i] = 2 * (v[i + 1] - v[i]); 
	for(int i = 0; i < n - 1; ++i)
	  sl[i + 1] = sl[i] + d[i];
	for(int i = n - 2; i >= 0; --i)
	  sr[i] = sr[i + 1] + d[i];
	for(int i = 0; i < n - 1; ++i)
	  ckmin(sl[i], v[i] - v.front());
	for(int i = 0; i < n - 1; ++i)
	  ckmin(sr[i], v.back() - v[i]);
	int ans = 1e9;
	for(int i = 0; i < n; ++i)
	  ckmin(ans, sl[i] + sr[i]);
	return ans + v.back() - v.front();
}
int main() {
	n = read(), m = read();
	vector<int> L(n + 1), R(n + 1);
	int mi = n, ma = -1;
	for(int x, y, siz, i = 0; i < m; ++i) {
		x = read(), siz = read();
		while(siz--){
			y = read();
			if(x != y) {
				ckmin(mi, min(x, y));
				ckmax(ma, max(x, y));
			}
			if(y < x){
				++L[y];
				--L[x];
			}
			if(x < y){
				++R[x];
				--R[y];
			}
		}
	}
	for(int i = 0; i < n; ++i) {
		L[i + 1] += L[i];
		R[i + 1] += R[i];
		if(L[i] != 0)
		  L[i] = 1;
		if(R[i] != 0)
		  R[i] = 1;
	}
	vector<int> vl, vr;
	int pl = 0, pr = 0;
	for(int i = 0; i < n; ++i){
		if(i == mi || i == ma){
		    vl.push_back(i); 
		    vl.push_back(i); 
		    vr.push_back(i);
		    vr.push_back(i);
		}
		if(L[i] != pl)
		  vl.push_back(i);
		if(R[i] != pr)
		  vr.push_back(i);
		pl = L[i], pr = R[i];
	}
	write(min(f(vl), f(vr)));
	return 0;
}
0