oj.uz

Submission #245657

# Submission time Handle Problem Language Result Execution time Memory
245657 2020-07-07T04:52:15 Z Mercenary Transport (COCI19_transport) C++14
0 / 130
 800 ms 25076 KB 
#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;

void dfs1(int u , int par , ll cur , ll need , ll cur1){
    val.pb(u);
    need = min(need , cur);
    cur += a[u];
    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];
//    cout << u << endl;
    val.clear();
    dfs1(u , 0 , 0 , 0 , 0);
    vis[u] = 1;
    ordered_set s;
    for(auto &c : val){
        if(::c[c] - a[u] >= 0)res += s.order_of_key(mp(::c[c] - a[u] + 1 , 0));
        s.insert(mp(-b[c] , c));
    }
    s.clear();
    reverse(val.begin(),val.end());
    for(auto& c : val){
        if(::c[c] - a[u] >= 0)res += s.order_of_key(mp(::c[c] - a[u] + 1 , 0));
        s.insert(mp(-b[c] , c));
    }
//    for(int i = 1 ; i <= n ; ++i){
//        cout << b[i] << " " << c[i] << endl;
//    }
    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

transport.cpp: In function 'int main()':
transport.cpp:85: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:86: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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 3200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 3840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 303 ms 14056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 415 ms 18552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 594 ms 24028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 183 ms 8824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 11636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 428 ms 14452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 527 ms 19212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 800 ms 25076 KB Output isn't correct
2 Halted 0 ms 0 KB -