제출 #1284069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284069		quan606303	Construction Project 2 (JOI24_ho_t2)	C++20	0 / 100	2 ms	568 KiB

Main

/*
 * @Author: RMQuan 
 * @Date: 2025-10-27 21:21:38 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-10-27 22:25:08
 */
/*idea : 



*/
#include <bits/stdc++.h>
bool M1;
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define TASK "TEST"
#define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
using namespace std;
const int MOD=1e9+7;
const int maxn=2e5+7;
const int inf=1e18;
vector<pair<int,int> > adj[maxn];
int n,m,S,T,L,K;
int dis[maxn][2];
bool vst[maxn][2];
void dij(int s,int type)
{
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    for (int i=1;i<=n;i++)dis[i][type]=inf;
    dis[s][type]=0;
    q.push({0,s});
    while (q.size())
    {
        int u=q.top().se;
        q.pop();
        if (vst[u][type])continue;
        vst[u][type]=true;
        for (auto v:adj[u])
        {
            if (dis[v.fi][type]>dis[u][type]+v.se)
            {
                dis[v.fi][type]=dis[u][type]+v.se;
                q.push({dis[v.fi][type],v.fi});
            }
        }
    }
}
bool cmp1(int x,int y)
{
    return dis[x][0]<dis[y][0];
}
bool cmp2(int x,int y)
{
    return dis[x][1]<dis[y][1];
}
bool cmp3(int x,int y)
{
    return dis[x][0]-dis[x][1]<dis[y][0]-dis[y][1];
}
struct BIT
{
    int N;
    vector<int> bit;
    BIT(int n):N(n),bit(n+5,0){}
    void upd(int x,int val)
    {
        for (;x<=N;x+=(x&-x))bit[x]+=val;
    }
    int get(int x)
    {
        int sum=0;
        for (;x>0;x&=(x-1))sum+=bit[x];
        return sum;
    }
};
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    file();
    cin>>n>>m>>S>>T>>L>>K;
    for (int i=1;i<=m;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
    }
    dij(S,0);
    dij(T,1);
    vector<int> node;
    for (int i=1;i<=n;i++)node.push_back(i);
    sort(node.begin(),node.end(),cmp3);
    vector<int> nen;
    nen.push_back(-1e18);
    if (dis[0][T]<=K)
    {
        cout<<n*(n-1)/2;
        return 0;
    }
    for (int i=1;i<=n;i++)
    {
        nen.push_back(dis[i][0]);
        nen.push_back(K-L-dis[i][1]);
        nen.push_back(dis[i][1]);
        nen.push_back(K-L-dis[i][0]);
    }
    sort(nen.begin(),nen.end());
    nen.erase(unique(nen.begin(),nen.end()),nen.end());
    BIT bit(nen.size()+5);
    int ans=0;
    for (auto i:node)
    {
        ans+=bit.get(lower_bound(nen.begin(),nen.end(),K-L-dis[i][1])-nen.begin());
        bit.upd(lower_bound(nen.begin(),nen.end(),dis[i][0])-nen.begin(),1);
    }
    cout<<ans;
    bool M2;
    cerr<<"-------------------------------------------------"<<endl;
    cerr<<"Time : "<<clock()<<" ms"<<endl;
    cerr<<"Memory : "<<abs(&M2-&M1)/1024/1024<<" MB"<<endl;
    cerr<<"-------------------------------------------------"<<endl;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int32_t main()':
Main.cpp:25:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:89:5: note: in expansion of macro 'file'
   89 |     file();
      |     ^~~~
Main.cpp:25:81: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:89:5: note: in expansion of macro 'file'
   89 |     file();
      |     ^~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 16
• Subtask 3: 0 / 29
• Subtask 4: 0 / 47