oj.uz

답안 #998908

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
998908 2024-06-14T22:39:46 Z whatthemomooofun1729 Pipes (BOI13_pipes) C++17
35 / 100
 1000 ms 10200 KB 
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#include <numeric>
#include <bitset>
#include <sstream>
#include <chrono>
#include <random>

#define ff first
#define ss second
#define PB push_back
#define sz(x) int(x.size())
#define rsz resize
#define fch(xxx, yyy) for (auto xxx : yyy) // abusive notation
#define all(x) (x).begin(),(x).end()
#define eps 1e-9

// more abusive notation (use at your own risk):
//#define int ll

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

// debugging
void __print(int x) {std::cerr << x;}
void __print(ll x) {std::cerr << x;} /* remember to uncomment this when not using THE MACRO */
void __print(unsigned x) {std::cerr << x;}
void __print(ull x) {std::cerr << x;}
void __print(float x) {std::cerr << x;}
void __print(double x) {std::cerr << x;}
void __print(ld x) {std::cerr << x;}
void __print(char x) {std::cerr << '\'' << x << '\'';}
void __print(const char *x) {std::cerr << '\"' << x << '\"';}
void __print(const string& x) {std::cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V> void __print(const pair<T, V> &x) {std::cerr << '{'; __print(x.ff); std::cerr << ", "; __print(x.ss); std::cerr << '}';}
template<typename T> void __print(const T& x) {int f = 0; std::cerr << '{'; for (auto &i: x) std::cerr << (f++ ? ", " : ""), __print(i); std::cerr << "}";}
void _print() {std::cerr << "]\n";}
template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) std::cerr << ", "; _print(v...);}
void println() {std::cerr << ">--------------------<" << endl;}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

// templates
template <class T> bool ckmin(T &a, const T &b) {return b<a ? a = b, 1 : 0;}
template <class T> bool ckmax(T &a, const T &b) {return b>a ? a = b, 1 : 0;}
template <class T> using gr = greater<T>;
template <class T> using vc = vector<T>;
template <class T> using p_q = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vc<T>, gr<T>>;
template <class T1, class T2> using pr = pair<T1, T2>;
mt19937_64 rng_ll(chrono::steady_clock::now().time_since_epoch().count());
int rng(int M) {return (int)(rng_ll()%M);} /*returns any random number in [0, M) */

// const variables
constexpr int INF = (int)2e9;
constexpr int MOD = 998244353;
constexpr ll LL_INF = (ll)3e18;
constexpr int mod = (int)1e9 + 7;
constexpr ll inverse = 500000004LL; // inverse of 2 modulo 1e9 + 7

void setIO(const string& str) {// fast input/output
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (str.empty()) return;
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
}

int N, M;
vc<vc<pii>> adj;
vi deg, vst, c, x;

signed main() { // TIME YOURSELF !!!
    setIO("");
    cin >> N >> M;
    adj.rsz(N+1), deg.rsz(N+1, 0), vst.rsz(N+1, 0), c.rsz(N+1), x.rsz(M);
    if (M > N) {
        cout << 0;
        return 0;
    }
    for (int i = 1; i <= N; ++i) {
        cin >> c[i];
    }
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].PB({b, i});
        adj[b].PB({a, i});
        deg[a]++, deg[b]++;
    }
    queue<int> q;
    for (int i = 1; i <= N; ++i) {
        if (deg[i] == 1) {
            vst[i] = 1;
            q.push(i);
        }
    }
    int n = N;
    while (!q.empty()) {
        int v = q.front(); // 'tis a leaf
        q.pop();
        n--;
        fch(to, adj[v]) {
            int u = to.ff;
            if (!vst[u]) {
                x[to.ss] = c[v];
                c[v] -= x[to.ss], c[u] -= x[to.ss];
                deg[u]--;
                if (deg[u] == 1) {
                    vst[u] = 1;
                    q.push(u);
                }
            }
        }
    }
    if (n == 0) {
        for (int i = 0; i < M; ++i) {
            cout << 2 * x[i] << '\n';
        }
    } else {
        int start = -1;
        vc<pii> f(N+1);
        for (int i = 1; i <= N; ++i) {
            if (!vst[i]) {
                start = i;
                break;
            }
        }
        q.push(start);
        int vert, L = 1;
        while (!q.empty()) {
            int v = q.front();
            vert = v;
            q.pop();
            vst[v] = 1;
            fch(u, adj[v]) if (!vst[u.ff]) {
                f[v] = u;
                q.push(u.ff);
            }
        }
        fch(u, adj[vert]) {
            if (u.ff == start) f[vert] = u;
        }
        int t = f[start].ff, sum = 0, factor = 1;
        while (t != start) {
            L++;
            sum += factor * c[t];
            t = f[t].ff;
            factor *= -1;
        }
        if (L%2 == 0) {
            cout << 0;
            return 0;
        }
        sum >>= 1;
        x[f[start].ss] = sum;
        int w = sum;
        t = f[start].ff;
        while (t != start) {
            x[f[t].ss] = c[t] - w;
            t = f[t].ff;
            w = x[f[t].ss];
        }
        for (int i = 0; i < M; ++i) {
            cout << 2 * x[i] << '\n';
        }
    }
    return 0;
}

// TLE -> TRY NOT USING DEFINE INT LONG LONG
// CE -> CHECK LINE 45
// 5000 * 5000 size matrices are kinda big (potential mle)
// Do something, start simpler

Compilation message

pipes.cpp: In function 'void setIO(const string&)':
pipes.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:164:24: warning: 'vert' may be used uninitialized in this function [-Wmaybe-uninitialized]
  164 |         fch(u, adj[vert]) {
      |                        ^

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 36 ms 10128 KB Output isn't correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Incorrect 1 ms 344 KB Output isn't correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Incorrect 31 ms 8276 KB Output isn't correct
14 Incorrect 43 ms 9556 KB Output isn't correct
15 Incorrect 41 ms 10064 KB Output isn't correct
16 Incorrect 32 ms 8788 KB Output isn't correct
17 Incorrect 35 ms 10176 KB Output isn't correct
18 Incorrect 36 ms 10200 KB Output isn't correct
19 Incorrect 33 ms 8016 KB Output isn't correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Incorrect 1 ms 348 KB Output isn't correct
22 Incorrect 37 ms 8740 KB Output isn't correct
23 Incorrect 31 ms 7004 KB Output isn't correct
24 Incorrect 34 ms 8736 KB Output isn't correct
25 Incorrect 29 ms 7260 KB Output isn't correct

Subtask #2
35.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1064 ms 348 KB Time limit exceeded
2 Execution timed out 1052 ms 348 KB Time limit exceeded
3 Execution timed out 1079 ms 8284 KB Time limit exceeded
4 Correct 1 ms 4184 KB Output is correct
5 Correct 1 ms 4188 KB Output is correct
6 Correct 2 ms 5720 KB Output is correct
7 Execution timed out 1100 ms 348 KB Time limit exceeded
8 Execution timed out 1060 ms 348 KB Time limit exceeded
9 Execution timed out 1051 ms 352 KB Time limit exceeded
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Execution timed out 1096 ms 348 KB Time limit exceeded
15 Execution timed out 1051 ms 348 KB Time limit exceeded
16 Execution timed out 1040 ms 344 KB Time limit exceeded
17 Execution timed out 1058 ms 344 KB Time limit exceeded
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Execution timed out 1098 ms 348 KB Time limit exceeded
23 Execution timed out 1052 ms 7004 KB Time limit exceeded
24 Execution timed out 1080 ms 8532 KB Time limit exceeded
25 Execution timed out 1041 ms 8276 KB Time limit exceeded
26 Correct 2 ms 4188 KB Output is correct
27 Correct 2 ms 4188 KB Output is correct
28 Correct 2 ms 4188 KB Output is correct
29 Correct 2 ms 5468 KB Output is correct
30 Execution timed out 1100 ms 8124 KB Time limit exceeded
31 Execution timed out 1073 ms 8284 KB Time limit exceeded
32 Execution timed out 1053 ms 8736 KB Time limit exceeded
33 Execution timed out 1036 ms 8528 KB Time limit exceeded
34 Correct 2 ms 4184 KB Output is correct
35 Correct 2 ms 4144 KB Output is correct
36 Correct 2 ms 4188 KB Output is correct
37 Correct 3 ms 5724 KB Output is correct
38 Execution timed out 1006 ms 8284 KB Time limit exceeded
39 Execution timed out 1087 ms 8784 KB Time limit exceeded
40 Execution timed out 1063 ms 8532 KB Time limit exceeded
41 Execution timed out 1044 ms 8228 KB Time limit exceeded
42 Correct 2 ms 4184 KB Output is correct
43 Correct 2 ms 4188 KB Output is correct
44 Correct 2 ms 4188 KB Output is correct
45 Correct 3 ms 3928 KB Output is correct
46 Execution timed out 1100 ms 8224 KB Time limit exceeded
47 Execution timed out 1055 ms 8616 KB Time limit exceeded
48 Execution timed out 1049 ms 8272 KB Time limit exceeded
49 Execution timed out 1045 ms 8492 KB Time limit exceeded
50 Correct 2 ms 4184 KB Output is correct
51 Correct 2 ms 4188 KB Output is correct
52 Correct 2 ms 4188 KB Output is correct
53 Correct 2 ms 4444 KB Output is correct
54 Execution timed out 1100 ms 8256 KB Time limit exceeded