oj.uz

답안 #245673

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245673 2020-07-07T05:54:01 Z Mercenary Transport (COCI19_transport) C++14
130 / 130
 626 ms 23024 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;
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

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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 3200 KB Output is correct
2 Correct 16 ms 3432 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 3456 KB Output is correct
2 Correct 24 ms 3712 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 10744 KB Output is correct
2 Correct 193 ms 10616 KB Output is correct

Subtask #4
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 310 ms 13568 KB Output is correct
2 Correct 335 ms 16348 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 451 ms 17396 KB Output is correct
2 Correct 540 ms 23024 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 6648 KB Output is correct
2 Correct 90 ms 6648 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 9332 KB Output is correct
2 Correct 254 ms 9464 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 343 ms 11252 KB Output is correct
2 Correct 327 ms 13044 KB Output is correct

Subtask #9
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 457 ms 13552 KB Output is correct
2 Correct 458 ms 15732 KB Output is correct

Subtask #10
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 626 ms 16792 KB Output is correct
2 Correct 563 ms 17524 KB Output is correct