Submission #245673

#	Time	Username	Problem	Language	Result	Execution time	Memory
245673		Mercenary	Transport (COCI19_transport)	C++14	130 / 130	626 ms	23024 KiB

Main

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <pair<ll,int>,null_type,less<pair<ll,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int logn = log2(maxn) + 1;

bool vis[maxn];
vector<ii> adj[maxn];
int sub[maxn] , big[maxn];

void dfs(int u , int par){
    sub[u] = 1;
    big[u] = -1;
    for(auto & c : adj[u]){
        if(vis[c.first] || c.first == par)continue;
        dfs(c.first , u);
        sub[u] += sub[c.first];
        if(big[u] == -1 || sub[big[u]] < sub[c.first])big[u] = c.first;
    }
}
ll res = 0;
int n , a[maxn];
ll b[maxn] , c[maxn];
vector<int> val;
int P[maxn];

void dfs1(int u , int par , ll cur , ll need , ll cur1){
    val.pb(u);
    need = min(need , cur);
    cur += a[u];
    if(par != 0 && P[par] == 0)P[u] = u;
    else P[u] = P[par];
//    cout << u << " " << P[u] << endl;
    if(cur1 < 0)c[u] = -1;
    else c[u] = cur;
    b[u] = need;
    for(auto c : adj[u]){
        if(c.first == par || vis[c.first] == 1)continue;
        dfs1(c.first , u , cur - c.second , need , min(0ll , cur1) + a[c.first] - c.second);
    }
}

void solve(int u){
    dfs(u , 0);
    int tot = sub[u];
    while(big[u] != -1 && sub[big[u]] * 2 >= tot)u = big[u];
    val.clear();
    dfs1(u , 0 , 0 , 0 , 0);
    vis[u] = 1;
    ordered_set s;
    int j = 0;
    for(auto &c : val){
        while(j < val.size() && P[c] != P[val[j]])s.insert(mp(-b[val[j]] , val[j])) , ++j;
        if(::c[c] - a[u] >= 0)res += s.order_of_key(mp(::c[c] - a[u] + 1 , 0));
    }
    s.clear();
    j = 0;
    reverse(val.begin(),val.end());
    for(auto &c : val){
        while(j < val.size() && P[c] != P[val[j]])s.insert(mp(-b[val[j]] , val[j])) , ++j;
        if(::c[c] - a[u] >= 0)res += s.order_of_key(mp(::c[c] - a[u] + 1 , 0));
    }
//    cout << "S " << u << endl;
//    cout << res << endl;
//    for(auto & c : val)cout << c << " " << b[c] << " " << ::c[c] - a[u] << " " << P[c] << endl;
//    for(int i = 1 ; i <= n ; ++i)cout << b[i] << " " << c[i] << endl;
    s.clear();
    for(auto c : adj[u]){
        if(vis[c.first] == 0)solve(c.first);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)cin >> a[i];
    for(int i = 1 ; i < n ; ++i){
        int u , v , c;cin >> u >> v >> c;
        adj[u].pb(mp(v , c));
        adj[v].pb(mp(u , c));
    }
    solve(1);
    cout << res;
}

Compilation message (stderr)

transport.cpp: In function 'void solve(int)':
transport.cpp:67:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j < val.size() && P[c] != P[val[j]])s.insert(mp(-b[val[j]] , val[j])) , ++j;
               ~~^~~~~~~~~~~~
transport.cpp:74:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j < val.size() && P[c] != P[val[j]])s.insert(mp(-b[val[j]] , val[j])) , ++j;
               ~~^~~~~~~~~~~~
transport.cpp: In function 'int main()':
transport.cpp:92:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
transport.cpp:93:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13