logoChat01.ai

#include <bits/stdc++.h> using namespace std; cons...

생성일: 2026년 7월 8일

답변에 사용된 모델 GPT-5.5 Thinking by Chat01

질문

#include <bits/stdc++.h>
using namespace std;
const int MAXN=200005;
const int MOD=1e9+7;
int n,Q,s,lef[MAXN],idx,rtlef;
bool visDFS[2000005],cget[MAXN],islf[2000005];
long long f[2000005],cnt[2000005],nodeval[2000005];
vector <int> v[2000005];
vector <long long> w[2000005];
struct Tree
{
int l,r,ls,rs;
}tr[2000005];
struct Node
{
int l,r,id;
}a[MAXN];
int idlf[2000005];
bool cmp(Node x,Node y) {
return x.l<y.l;
}
int Buildgraph1(int fa,int l,int r)
{
int p=++idx;
tr[p].l=l,tr[p].r=r;
if (l==r) {
lef[l]=p;
nodeval[p]=-a[l].l;
islf[p]=1;
idlf[p]=l;
} else {
nodeval[p]=0;
}
if (fa!=0)
{
v[fa].push_back(p);
w[fa].push_back(nodeval[p]);
}
if (l==r) return p;
int midd=(l+r)/2;
tr[p].ls=Buildgraph1(p,l,midd);tr[p].rs=Buildgraph1(p,midd+1,r);
return p;
}
void add(int p,int vto,int ll,int rr,long long ww,int opt)
{
if (ll<=tr[p].l&&tr[p].r<=rr)
{
if (opt==1)
{
v[vto].push_back(p);
w[vto].push_back(ww+nodeval[p]);
}
else
{
v[p].push_back(vto);
w[p].push_back(ww+nodeval[vto]);
}
return;
}
int midd=(tr[p].l+tr[p].r)/2;
if (ll<=midd) add(tr[p].ls,vto,ll,rr,ww,opt);
if (midd<rr) add(tr[p].rs,vto,ll,rr,ww,opt);
}
void dfs(int u)
{
if (visDFS[u]) return;
visDFS[u]=1;
f[u]=2e18;
cnt[u]=0;
if (islf[u])
{
int k=idlf[u];
if (!cget[k])
{
f[u]=a[k].r;
cnt[u]=1;
}
}
for (int i=0;i<v[u].size();i++)
{
int vto=v[u][i];
long long weight=w[u][i];
dfs(vto);
if (f[vto]==2e18) continue;

text
	if (f[vto]+weight<f[u])
	{
		f[u]=f[vto]+weight;
		cnt[u]=cnt[vto];
	}
	else if (f[vto]+weight==f[u])
	{
		cnt[u]=(cnt[u]+cnt[vto])%MOD;
	}
}

}
void dijk()
{
long long minans=2e18;
long long answ=0;

text
for (int i=1;i<=n;i++)
{
	dfs(lef[i]);
	if (f[lef[i]]<minans)
	{
		minans=f[lef[i]];
		answ=cnt[lef[i]];
	}
	else if (f[lef[i]]==minans)
	{
		answ=(answ+cnt[lef[i]])%MOD;
	}
}
cout<<answ<<'\n';

}
int main()
{
cin>>n;
for (int i=1;i<=n;i++) {
cin>>a[i].l>>a[i].r;
a[i].id=i;
}
sort(a+1,a+1+n,cmp);
rtlef=Buildgraph1(0,1,n);
for (int i=1;i<=n;i++) {
int lget=a[i].r;
int leftt=1,rightt=n;
int target=0;
while (leftt<=rightt) {
int midd=(leftt+rightt)/2;
if (a[midd].l<=lget) {
target=midd;
leftt=midd+1;
}
else rightt=midd-1;
}
if (target>=1) {
cget[i]=1;
add(rtlef,lef[i],1,target,a[i].r,1);
} else {
cget[i]=0;
}
}
dijk();
return 0;
}https://www.luogu.com.cn/problem/CF1197E 最小限度DEBUG代码，不加注释，保留代码风格与格式

사고

undefined

사고

Verifying handling of equal items in path selection

For identical items in the graph, order matters when selecting among equal inner items. If two dolls have the same inner but different outer values, the valid choices depend on the chains they form. Since out > in, two cannot be part of the same chain. I'll verify this by checking random tests and C++ implementation.

Thought for 3m 7s

답변

题面输入是 out_i in_i，嵌套条件是 out_i <= in_j，所以这里改成 r=out, l=in 后按 l 排序，再做 DAG 最短路计数。(luogu.com.cn)

cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN=200005;
const int MOD=1e9+7;
int n,Q,s;
long long f[MAXN],cnt[MAXN];
vector <int> v[MAXN];
vector <long long> w[MAXN];
struct Node
{
	int l,r,id;
}a[MAXN];
bool cmp(Node x,Node y) {
	return x.l<y.l;
}
void dijk()
{
	for (int i=0;i<=n;i++)
	{
		f[i]=2e18;
		cnt[i]=0;
	}
	f[0]=0;
	cnt[0]=1;
	for (int i=0;i<=n;i++)
	{
		for (int j=0;j<v[i].size();j++)
		{
			int vto=v[i][j];
			long long weight=w[i][j];
			if (f[i]+weight<f[vto])
			{
				f[vto]=f[i]+weight;
				cnt[vto]=cnt[i];
			}
			else if (f[i]+weight==f[vto])
			{
				cnt[vto]=(cnt[vto]+cnt[i])%MOD;
			}
		}
	}
	long long minans=2e18;
	long long answ=0;
	for (int i=1;i<=n;i++)
	{
		if (a[i].r>a[n].l)
		{
			if (f[i]<minans)
			{
				minans=f[i];
				answ=cnt[i];
			}
			else if (f[i]==minans)
			{
				answ=(answ+cnt[i])%MOD;
			}
		}
	}
	cout<<answ<<'\n';
}
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>a[i].r>>a[i].l;
		a[i].id=i;
	}
	sort(a+1,a+1+n,cmp);
	for (int i=0;i<n;i++) {
		v[i].push_back(i+1);
		w[i].push_back(a[i+1].l-a[i].l);
	}
	for (int i=1;i<=n;i++) {
		int leftt=1,rightt=n;
		int target=n+1;
		while (leftt<=rightt) {
			int midd=(leftt+rightt)/2;
			if (a[midd].l>=a[i].r) {
				target=midd;
				rightt=midd-1;
			}
			else leftt=midd+1;
		}
		if (target<=n) {
			v[i].push_back(target);
			w[i].push_back(a[target].l-a[i].r);
		}
	}
	dijk();
	return 0;
}

이 Q&A 공유하기