Submission #1297785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297785		quanduongxuan12	Toll (BOI17_toll)	C++20	7 / 100	3095 ms	15772 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[MAXN];
vector<ii> adj[MAXN];
namespace task1{
    int len;
    int root[MAXN];
    int depth[MAXN];
    int times=0;
    ii cnt[MAXN];
    const int LOG=15;
    int anc[MAXN][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{
    bool mark[MAXN];
    map<int, int> d[MAXN];
    int in[MAXN];
    void dfs(int u){
        for (ii pairs:adj[u]){
            int v=pairs.fs;
            ++in[v];
            dfs(v);
        }
    }
    queue<int> Q;
    void calc(int p){
        dfs(p);
        Q.push(p);
        while (Q.size()){
            int u=Q.front();
            Q.pop();
            for (ii pairs:adj[u]){
                int v=pairs.fs;
                int w=pairs.sc;
                if (d[p][v]==0||d[p][v]>d[p][u]+w) d[p][v]=d[p][u]+w;
                if (--in[v]==0) Q.push(v);
            }
        }
    }
    void solve(){
        FOR(i,1,q) mark[query[i].fs]=1;
        FOR(i,1,n){
            if (mark[i]) calc(i);
        }
        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 task2::solve();
    return 0;
}

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