oj.uz

답안 #1059449

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1059449 2024-08-15T01:27:41 Z Edu175 봉쇄 시간 (IOI23_closing) C++17
0 / 100
 104 ms 70632 KB 
#include "closing.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,jet=b;i<jet;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define imp(v) {for(auto gdljh:v)cout<<gdljh<<" "; cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=2e5+5,INF=1e15;

vector<ll> d[2];
ll b[MAXN][2];
ll n,k;
vector<ii> g[MAXN];
void dfs(ll x, vector<ll> &d){
	for(auto [y,w]:g[x])if(d[y]==-1){
		d[y]=d[x]+w;
		dfs(y,d);
	}
}
ll disjoint(){
	vector<ll>v;
	fore(i,0,n)v.pb(b[i][0]);
	sort(ALL(v));
	ll ki=0,res=0;
	// imp(v);
	fore(i,0,SZ(v)){
		if(ki+v[i]<=k)res++,ki+=v[i];
	}
	return res;
}

ll x,y;
bool can(ll c){
	vector<ll>bd;
	fore(i,0,n)bd.pb(b[i][1]);
	sort(ALL(bd));
	ll res=INF;
	fore(l,0,x+1){
		set<ll>st;
		ll resi=0;
		fore(r,y+1,n+1){
			st.insert(b[r-1][1]);
			resi+=b[r-1][0];
			if(!(r-l<=c&&c<=2*(r-l)))continue;
			ll ci=0,add=0;
			for(auto i:st){
				if(ci>=c-(r-l))break;
				add+=i; ci++;
			}
			assert(c==ci+r-l);
			res=min(res,resi+add);
		}
	}
	return res<=k;
}
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
	n=N,k=K,x=X,y=Y;
	fore(i,0,n){
		g[i].clear();
	}
	
	fore(i,0,n-1){
		g[U[i]].pb({V[i],W[i]});
		g[V[i]].pb({U[i],W[i]});
	}
	d[0]=d[1]=vector<ll>(n,-1);
	d[0][x]=0; dfs(x,d[0]);
	d[1][y]=0; dfs(y,d[1]);
	fore(i,0,n){
		auto &x=b[i][0],&y=b[i][1];
		x=d[0][i];
		y=d[1][i];
		if(x>y)swap(x,y);
		y-=x;
	}
	ll res=disjoint();
	ll m=y-x+1;
	ll l=m,r=n-1;
	while(l<=r){
		ll m=(l+r)/2;
		if(can(m))l=m+1;
		else r=m-1;
	}
	// cout<<r<<" r\n";
	if(r>=m)res=max(res,r);
	
	
    return res;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 13404 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 104 ms 70632 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Runtime error 5 ms 13236 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Runtime error 5 ms 13236 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Runtime error 5 ms 13236 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 13404 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 13404 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 13404 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 13404 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 13404 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -