Submission #1243562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243562		letronghung	Cloud Computing (CEOI18_clo)	C++17	0 / 100	3 ms	4936 KiB

clo

#include <bits/stdc++.h>
using  namespace std;
#define ll long long
#define fr(i,a,b) for(int i=a;i<=b;i++)

ll const maxN=1e5+5;
ll n,m,cnt=0,tpltm[maxN],id=0;
ll a[maxN],low[maxN],num[maxN],dem[maxN],dp[maxN];
bool dele[maxN];
stack<ll> st;
vector<ll> g[maxN],sum_of_coin,final_graph[maxN];

void dfs(ll u){
    low[u]=num[u]=cnt++;
    st.push(u);
    for(ll v:g[u]){
        if(dele[v]) continue;
        if(!num[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else low[u]=min(low[u],num[v]);
    }
    if(num[u]==low[u]){
        ll sum=0;
        while(1){
           ll v=st.top();
           st.pop();
           dele[v]=true;
           tpltm[v]=id;
           sum+=a[v];
           if(v==u) break;
        }
        id++;
        sum_of_coin.push_back(sum);
    }
}

int main(){
    cin>> n>> m;
    fr(i,1,n){
        cin>>a[i];
    }
    fr(i,1,m){
        ll x,y;
        cin>>x>>y;
        g[x].push_back(y);
    }
    fr(i,1,n){
        if(!num[i]) dfs(i);
    }
    set<pair<ll,ll>> dathem;
    fr(i,1,n){
        for(ll v : g[i]){
            ll x=tpltm[i],y=tpltm[v];
            if(x!=y && !dathem.count({x,y})){
                final_graph[x].push_back(y);
                dathem.insert({x,y});
            }
        }
    }
    fr(i,0,id-1){
        for(ll v:final_graph[i]){
            dem[v]++;
        }
    }
    queue<ll> q;
    fr(i,0,id-1){
        if(dem[i]==0){
            dp[i]=sum_of_coin[i];
            q.push(i);
        }
    }
    while(!q.empty()){
        ll u=q.front();
        q.pop();
        for(ll v:final_graph[u]){
            dp[v]=max(dp[v],dp[u]+sum_of_coin[v]);
            dem[v]--;
            if(dem[v]==0){
                q.push(v);
            }
        }
    }
    cout<< *max_element(dp,dp+id);
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 18
• Subtask 3: 0 / 18
• Subtask 4: 0 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10