| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 462276 |
2021-08-10T09:44:32 Z |
Yeboi |
Pipes (BOI13_pipes) |
C++14 |
|
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()){
| ^~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
