Submission #1297825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297825		quanduongxuan12	Toll (BOI17_toll)	C++20	7 / 100	1466 ms	589824 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define name "optcost"
#define MAXN 100005
#define pb push_back
#define pf push_front
#define ll long long
#define ii pair<int, int>
#define fs first
#define sc second
#define ill pair<int, ll>
#define lli pair<ll, int>
#define llll pair<ll, ll>
#define all(v) v.begin(),v.end()
#define uni(v) v.erase(unique(all(v)),v.end())
#define bit(n,i) (((n)>>(i))&1)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--)
#define MASK(i) (1LL<<(i))
const int INF=1e9;
const int MOD=1e9+7;
void add(int &u, int v){
    u+=v;
    if (u>=MOD) u-=MOD;
}
void sub(int &u, int v){
    u-=v;
    if (u<0) u+=MOD;
}
void minimize(int &u, int v){
    u=min(u,v);
}
void maximize(int &u, int v){
    u=max(u,v);
}
long long Rand(long long l, long long r){
    ll tmp=0;
    FOR(i,1,4) tmp=((tmp<<15)^(((1<<15)-1)&rand()));
    return l+tmp%(r-l+1);
}
int k,n,m,q;
struct Edge{
    int x,y,w;
}e[MAXN];
ii query[(int)1e4+7];
vector<ii> adj[(int)5e4+7];
namespace task1{
    int len;
    int root[(int)5e4+7];
    int depth[(int)5e4+7];
    int times=0;
    ii cnt[(int)5e4+7];
    const int LOG=15;
    int anc[(int)5e4+7][LOG+1];
    void dfs(int u){
        root[u]=len;
        cnt[u].fs=++times;
        for (ii pairs:adj[u]){
            int v=pairs.fs,w=pairs.sc;
            depth[v]=depth[u]+w;
            anc[v][0]=u;
            dfs(v);
        }
        cnt[u].sc=times;
    }
    bool check_ancestor(int u, int v){
        return cnt[u].fs<=cnt[v].fs&&cnt[v].fs<=cnt[u].sc;
    }
    int lca(int u, int v){
        if (check_ancestor(u,v)) return u;
        if (check_ancestor(v,u)) return v;
        FORD(i,LOG,0) if (anc[u][i]&&!check_ancestor(anc[u][i],v)) u=anc[u][i];
        return anc[u][0];
    }
    void solve(){
        memset(root,-1,sizeof(root));
        FOR(i,1,n){
            if (root[i]==-1){
                ++len;
                dfs(i);
            }
        }
        FOR(j,1,LOG) FOR(i,1,n) anc[i][j]=anc[anc[i][j-1]][j-1];
        FOR(id,1,q){
            int u=query[id].fs,v=query[id].sc;
            if (root[u]!=root[v]){
                cout<<-1<<"\n";
            }
            else{
                cout<<depth[u]+depth[v]-2*depth[lca(u,v)]<<"\n";
            }
        }
    }
}
namespace task2{
    map<int, int> d[(int)5e4+7];
    vector<int> cur,prev;
    //int times=0;
    void solve(){
        FORD(i,n,1){
            int j=i;
            while (j>=1&&(int)j/k==(int)i/k) --j;
            FOR(u,j+1,i){
                for (ii pairs:adj[u]){
                    int v=pairs.fs;
                    int w=pairs.sc;
                    d[u][v]=w;
                    for (int x:cur){
         //               ++times;
                        if (d[v][x]>0&&(d[u][x]==0||d[u][x]>d[v][x]+w)){
                            d[u][x]=d[v][x]+w;
                        }
                    }
                }
            }
            for (int u:prev) cur.pb(u);
            prev.clear();
            FOR(u,j+1,i) prev.pb(u);
            i=j+1;
        }
        FOR(i,1,q){
            int u=query[i].fs,v=query[i].sc;
            if (u==v){
                cout<<0<<"\n";
            }
            else{
                cout<<(d[u][v]==0?-1:d[u][v])<<"\n";
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>k>>n>>m>>q;
    FOR(i,1,m) cin>>e[i].x>>e[i].y>>e[i].w;
    FOR(i,1,q) cin>>query[i].fs>>query[i].sc;
    FOR(i,1,m){
        ++e[i].x;
        ++e[i].y;
    }
    FOR(i,1,q){
        ++query[i].fs;
        ++query[i].sc;
    }
    FOR(i,1,m){
        adj[e[i].x].pb({e[i].y,e[i].w});
    }
    if (k==1) task1::solve();
    else{
        if (m>(int)1e5) return -1;
        task2::solve();
    }
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44