답안 #462276

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
462276 2021-08-10T09:44:32 Z Yeboi Pipes (BOI13_pipes) C++14
44.0741 / 100
349 ms 32140 KB
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i,s) for(ll i=0; i<s ; i++)
#define f(i,a,b) for(ll i(a); i<b ; i++)
const ll INF = 1000000000000000000;
const ll N = 100001;
const ll MOD = 1000000007;
const ll modi = 1000000007;
const ll MAXN = 10000000000;    
const ll rootval = 319;
using namespace std;

ll upedge[N];
vector<ll> adj[N];
ll arr[N];
ll par[N];

void dfs(ll v, ll p){
    ll sum = 0;
    for(auto u : adj[v]){
        if(u == p){
            continue;
        }
        else{
            if(upedge[u] == -1){
                dfs(u,v);
                sum += upedge[u];
            }
        }
    }
    upedge[v] = arr[v] - sum;
}
void parent(ll v, ll p){
    for(auto u : adj[v]){
        if(u == p){
            continue;
        }
        else{
            par[u] = v;
            parent(u,v);
        }
    }
}
int main(){
    fastio();
    ll n,m;
    cin >> n >> m;
    vector<pair<ll,ll>> edges;
    rep(i,n){
        cin >> arr[i];
        upedge[i] = -1;
    }
    rep(i,m){
        ll u,v;
        cin >> u >> v;
        --u,--v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges.push_back(make_pair(u,v));
    }
    if(m == n-1){
        rep(i,n){
            if(adj[i].size() == 1){
                upedge[i] = arr[i];
            }
        }
        dfs(0,-1);
        parent(0,-1);
        par[0] = -1;
        map<pair<ll,ll>,ll> mp;
        rep(i,n){
            if(par[i] == -1){
                continue;
            }
            else{
                mp[{i,par[i]}] = upedge[i];
                mp[{par[i],i}] = upedge[i];
            }
        }
        rep(i,edges.size()){
            ll u = edges[i].first;
            ll v = edges[i].second;
            cout << 2*mp[{u,v}] << endl;
        }
    }
    else{
        cout << 0 << endl;
    }
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:5:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,s) for(ll i=0; i<s ; i++)
......
   82 |         rep(i,edges.size()){
      |             ~~~~~~~~~~~~~~     
pipes.cpp:82:9: note: in expansion of macro 'rep'
   82 |         rep(i,edges.size()){
      |         ^~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Incorrect 2 ms 2636 KB Output isn't correct
3 Incorrect 4 ms 2804 KB Output isn't correct
4 Incorrect 325 ms 24756 KB Output isn't correct
5 Incorrect 3 ms 2636 KB Output isn't correct
6 Incorrect 2 ms 2636 KB Output isn't correct
7 Incorrect 2 ms 2676 KB Output isn't correct
8 Incorrect 3 ms 2764 KB Output isn't correct
9 Incorrect 4 ms 2764 KB Output isn't correct
10 Incorrect 5 ms 2844 KB Output isn't correct
11 Incorrect 4 ms 2892 KB Output isn't correct
12 Incorrect 4 ms 2892 KB Output isn't correct
13 Incorrect 246 ms 20264 KB Output isn't correct
14 Incorrect 315 ms 23556 KB Output isn't correct
15 Incorrect 323 ms 25024 KB Output isn't correct
16 Incorrect 286 ms 21500 KB Output isn't correct
17 Incorrect 349 ms 24656 KB Output isn't correct
18 Incorrect 339 ms 24832 KB Output isn't correct
19 Incorrect 330 ms 28332 KB Output isn't correct
20 Incorrect 2 ms 2636 KB Output isn't correct
21 Incorrect 4 ms 2764 KB Output isn't correct
22 Incorrect 327 ms 24904 KB Output isn't correct
23 Incorrect 245 ms 20228 KB Output isn't correct
24 Incorrect 347 ms 24868 KB Output isn't correct
25 Incorrect 271 ms 21148 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2672 KB Output isn't correct
2 Incorrect 2 ms 2636 KB Output isn't correct
3 Correct 54 ms 10444 KB Output is correct
4 Correct 49 ms 10536 KB Output is correct
5 Correct 49 ms 10760 KB Output is correct
6 Correct 224 ms 32140 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Incorrect 2 ms 2636 KB Output isn't correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Incorrect 2 ms 2636 KB Output isn't correct
15 Incorrect 2 ms 2636 KB Output isn't correct
16 Incorrect 2 ms 2636 KB Output isn't correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 2 ms 2684 KB Output is correct
21 Correct 3 ms 2764 KB Output is correct
22 Incorrect 2 ms 2636 KB Output isn't correct
23 Incorrect 48 ms 9668 KB Output isn't correct
24 Incorrect 50 ms 10736 KB Output isn't correct
25 Correct 47 ms 10360 KB Output is correct
26 Correct 49 ms 10676 KB Output is correct
27 Correct 49 ms 10420 KB Output is correct
28 Correct 54 ms 11164 KB Output is correct
29 Correct 191 ms 26768 KB Output is correct
30 Incorrect 47 ms 10340 KB Output isn't correct
31 Incorrect 49 ms 10492 KB Output isn't correct
32 Incorrect 53 ms 11060 KB Output isn't correct
33 Correct 52 ms 10756 KB Output is correct
34 Correct 50 ms 10568 KB Output is correct
35 Correct 64 ms 10648 KB Output is correct
36 Correct 64 ms 10880 KB Output is correct
37 Correct 253 ms 32064 KB Output is correct
38 Incorrect 54 ms 10524 KB Output isn't correct
39 Incorrect 55 ms 10928 KB Output isn't correct
40 Incorrect 52 ms 10840 KB Output isn't correct
41 Correct 50 ms 10564 KB Output is correct
42 Correct 53 ms 10400 KB Output is correct
43 Correct 50 ms 10584 KB Output is correct
44 Correct 48 ms 10744 KB Output is correct
45 Correct 165 ms 27948 KB Output is correct
46 Incorrect 50 ms 10448 KB Output isn't correct
47 Incorrect 49 ms 10688 KB Output isn't correct
48 Incorrect 51 ms 10512 KB Output isn't correct
49 Correct 47 ms 10592 KB Output is correct
50 Correct 50 ms 10680 KB Output is correct
51 Correct 50 ms 10780 KB Output is correct
52 Correct 64 ms 10468 KB Output is correct
53 Correct 180 ms 28356 KB Output is correct
54 Incorrect 49 ms 10500 KB Output isn't correct