답안 #462438

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
462438 2021-08-10T14:36:36 Z Yeboi Pipes (BOI13_pipes) C++14
62.2222 / 100
497 ms 36856 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];
ll ngood[N];
vector<ll> adj[N];
ll arr[N];
ll par[N];
ll n;
void dfs1(ll v, ll p){
    ll sum = 0;
    for(auto u : adj[v]){
        if(u == p){
            continue;
        }
        else{
            if(upedge[u] == -1){
                dfs1(u,v);
                sum += upedge[u];
            }
        }
    }
    upedge[v] = arr[v] - sum;
}
void dfs2(ll v, ll p){
    ll sum = 0;
    for(auto u : adj[v]){
        if(u == p || ngood[u] == -1){
            continue;
        }
        else{
            if(upedge[u] == -1){
                dfs2(u,v);
                sum += upedge[u];
            }
        }
    }
    upedge[v] = arr[v] - sum;
}
void parents(ll v, ll p){
    for(auto u : adj[v]){
        if(u == p){
            continue;
        }
        else{
            par[u] = v;
            parents(u,v);
        }
    }
}
void parents2(ll v, ll p){
    for(auto u : adj[v]){
        if(u == p || ngood[u] == -1){
            continue;
        }
        else{
            par[u] = v;
            parents2(u,v);
        }
    }
}
vector<bool> visited;
vector<ll> parent;
ll cycle_start, cycle_end;

bool dfs(ll v, ll par) { // passing vertex and its parent vertex
    visited[v] = true;
    for (ll u : adj[v]) {
        if(u == par) continue; // skipping edge to parent vertex
        if (visited[u]) {
            cycle_end = v;
            cycle_start = u;
            return true;
        }
        parent[u] = v;
        if (dfs(u, parent[u]))
            return true;
    }
    return false;
}

vector<ll> find_cycle() {
    visited.assign(n, false);
    parent.assign(n, -1);
    cycle_start = -1;
    vector<ll> cycle;
    for (ll v = 0; v < n; v++) {
        if (!visited[v] && dfs(v, parent[v]))
            break;
    }

    if (cycle_start == -1) {
        return cycle;
    } else {
        vector<ll> cycle;
        cycle.push_back(cycle_start);
        for (ll v = cycle_end; v != cycle_start; v = parent[v]){
            cycle.push_back(v);
        }
        reverse(cycle.begin(), cycle.end());
        return cycle;
    }
}
int main(){
    fastio();
    ll 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];
            }
        }
        dfs1(0,-1);
        parents(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 if(m == n){
        // one cycle exists so just find that one cycle done?
        vector<ll> cycle = find_cycle();
        rep(i,cycle.size()){
            ngood[cycle[i]] = -1;
        }
        if(cycle.size() % 2 == 0){
            cout << 0 << endl;
        }
        else{
            rep(j,cycle.size()){
                ll i = cycle[j];
                    dfs2(i,-1);
                    parents2(i,-1);
                    par[i] = -1;
            }
            map<pair<ll,ll>,ll> mp;
            map<pair<ll,ll>,ll> mp2;
            rep(i,n){
                if(par[i] != -1){
                    mp[{par[i],i}] = upedge[i];
                    mp[{i,par[i]}] = upedge[i];
                    mp2[{par[i],i}] = 2*upedge[i];
                    mp2[{i,par[i]}] = 2*upedge[i];
                }
            }
            rep(i,cycle.size()){
                for(auto u : adj[cycle[i]]){
                    if(ngood[u] == -1){
                        continue;
                    }
                    else{
                        arr[cycle[i]] = arr[cycle[i]] - mp[{cycle[i],u}];
                    }
                }
            }
            ll val = arr[cycle[0]];
            f(i,1,cycle.size()){
                if(i%2 == 1){
                    val += arr[cycle[i]];
                }
                else{
                    val = val - arr[cycle[i]];
                }
            }
            mp2[{cycle[0],cycle[1]}] = val;
            f(i,1,cycle.size()-1){
                mp2[{cycle[i],cycle[i+1]}] = 2*arr[cycle[i]] - mp2[{cycle[i-1],cycle[i]}];
                mp2[{cycle[i+1],cycle[i]}] = mp2[{cycle[i],cycle[i+1]}];
            }
            mp2[{cycle[cycle.size()-1],cycle[0]}] = 2*arr[cycle[cycle.size()-1]] - mp2[{cycle[cycle.size()-1],cycle[cycle.size()-2]}];
            mp2[{cycle[0],cycle[cycle.size()-1]}] = mp2[{cycle[cycle.size()-1],cycle[0]}];
            rep(i,edges.size()){
                cout << mp2[{edges[i].first,edges[i].second}] << 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++)
......
  151 |         rep(i,edges.size()){
      |             ~~~~~~~~~~~~~~     
pipes.cpp:151:9: note: in expansion of macro 'rep'
  151 |         rep(i,edges.size()){
      |         ^~~
pipes.cpp:5:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,s) for(ll i=0; i<s ; i++)
......
  160 |         rep(i,cycle.size()){
      |             ~~~~~~~~~~~~~~     
pipes.cpp:160:9: note: in expansion of macro 'rep'
  160 |         rep(i,cycle.size()){
      |         ^~~
pipes.cpp:5:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,s) for(ll i=0; i<s ; i++)
......
  167 |             rep(j,cycle.size()){
      |                 ~~~~~~~~~~~~~~ 
pipes.cpp:167:13: note: in expansion of macro 'rep'
  167 |             rep(j,cycle.size()){
      |             ^~~
pipes.cpp:5:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,s) for(ll i=0; i<s ; i++)
......
  183 |             rep(i,cycle.size()){
      |                 ~~~~~~~~~~~~~~ 
pipes.cpp:183:13: note: in expansion of macro 'rep'
  183 |             rep(i,cycle.size()){
      |             ^~~
pipes.cpp:6:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define f(i,a,b) for(ll i(a); i<b ; i++)
......
  194 |             f(i,1,cycle.size()){
      |               ~~~~~~~~~~~~~~~~  
pipes.cpp:194:13: note: in expansion of macro 'f'
  194 |             f(i,1,cycle.size()){
      |             ^
pipes.cpp:6:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define f(i,a,b) for(ll i(a); i<b ; i++)
......
  203 |             f(i,1,cycle.size()-1){
      |               ~~~~~~~~~~~~~~~~~~
pipes.cpp:203:13: note: in expansion of macro 'f'
  203 |             f(i,1,cycle.size()-1){
      |             ^
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++)
......
  209 |             rep(i,edges.size()){
      |                 ~~~~~~~~~~~~~~ 
pipes.cpp:209:13: note: in expansion of macro 'rep'
  209 |             rep(i,edges.size()){
      |             ^~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Incorrect 3 ms 2636 KB Output isn't correct
3 Incorrect 5 ms 2824 KB Output isn't correct
4 Incorrect 329 ms 23672 KB Output isn't correct
5 Incorrect 2 ms 2636 KB Output isn't correct
6 Incorrect 2 ms 2636 KB Output isn't correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Incorrect 2 ms 2636 KB Output isn't correct
9 Incorrect 4 ms 2764 KB Output isn't correct
10 Incorrect 5 ms 2812 KB Output isn't correct
11 Incorrect 4 ms 2804 KB Output isn't correct
12 Incorrect 5 ms 2892 KB Output isn't correct
13 Incorrect 267 ms 19516 KB Output isn't correct
14 Incorrect 320 ms 22616 KB Output isn't correct
15 Incorrect 343 ms 23636 KB Output isn't correct
16 Incorrect 311 ms 20524 KB Output isn't correct
17 Incorrect 334 ms 23552 KB Output isn't correct
18 Incorrect 355 ms 23784 KB Output isn't correct
19 Incorrect 374 ms 27060 KB Output isn't correct
20 Incorrect 2 ms 2636 KB Output isn't correct
21 Incorrect 4 ms 2892 KB Output isn't correct
22 Incorrect 371 ms 23564 KB Output isn't correct
23 Incorrect 272 ms 19392 KB Output isn't correct
24 Incorrect 333 ms 23620 KB Output isn't correct
25 Incorrect 269 ms 20280 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 5 ms 2908 KB Output is correct
3 Correct 64 ms 13748 KB Output is correct
4 Correct 59 ms 9432 KB Output is correct
5 Correct 51 ms 9584 KB Output is correct
6 Correct 225 ms 26068 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is 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 2668 KB Output is correct
14 Incorrect 2 ms 2636 KB Output isn't correct
15 Correct 5 ms 2936 KB Output is correct
16 Correct 5 ms 2892 KB Output is correct
17 Correct 3 ms 2764 KB Output is correct
18 Correct 3 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 2 ms 2764 KB Output is correct
21 Correct 3 ms 2764 KB Output is correct
22 Correct 5 ms 3020 KB Output is correct
23 Incorrect 346 ms 27220 KB Output isn't correct
24 Correct 469 ms 33636 KB Output is correct
25 Correct 59 ms 13688 KB Output is correct
26 Correct 55 ms 9428 KB Output is correct
27 Correct 51 ms 9268 KB Output is correct
28 Correct 55 ms 9804 KB Output is correct
29 Correct 210 ms 21916 KB Output is correct
30 Incorrect 452 ms 35468 KB Output isn't correct
31 Incorrect 432 ms 31124 KB Output isn't correct
32 Correct 492 ms 36356 KB Output is correct
33 Correct 61 ms 14644 KB Output is correct
34 Correct 52 ms 9456 KB Output is correct
35 Correct 51 ms 9344 KB Output is correct
36 Correct 51 ms 9728 KB Output is correct
37 Correct 230 ms 26180 KB Output is correct
38 Correct 490 ms 34212 KB Output is correct
39 Correct 497 ms 36616 KB Output is correct
40 Correct 456 ms 34032 KB Output is correct
41 Correct 72 ms 16816 KB Output is correct
42 Correct 71 ms 9412 KB Output is correct
43 Correct 51 ms 9324 KB Output is correct
44 Correct 53 ms 9568 KB Output is correct
45 Correct 163 ms 22940 KB Output is correct
46 Incorrect 464 ms 36856 KB Output isn't correct
47 Correct 463 ms 33932 KB Output is correct
48 Correct 430 ms 31248 KB Output is correct
49 Correct 54 ms 11848 KB Output is correct
50 Correct 51 ms 9432 KB Output is correct
51 Correct 53 ms 9628 KB Output is correct
52 Correct 55 ms 9268 KB Output is correct
53 Correct 183 ms 23072 KB Output is correct
54 Incorrect 490 ms 35900 KB Output isn't correct