oj.uz

Submission #484693

# Submission time Handle Problem Language Result Execution time Memory
484693 2021-11-05T05:35:14 Z idas Pipes (BOI13_pipes) C++17
65 / 100
 400 ms 59468 KB 
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define F first
#define S second
#define PB push_back
#define MP make_pair

using namespace std;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pff;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;

const int INF=1e9, MOD=1e9+7;

void setIO()
{
    FAST_IO;
}

void setIO(string s)
{
    FAST_IO;
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int N=5e5+10;
int n, m;
ll c[N];
vi ad[N];
bool v[N];
map<pii, ll> x;
map<int, pii> con;

queue<int> q;
void bfs()
{
    while(!q.empty()){
        int u=q.front(); q.pop();
        if(v[u]) continue;
        v[u]=true;
        int cn=0;
        for(auto it : ad[u]){
            if(!x.count({it, u})) cn++;
        }
        if(cn>=2){
            v[u]=false;
            continue;
        }
        int in=-1;
        ll sm=0;
        for(auto it : ad[u]){
            if(!x.count({it, u})) in=it;
            sm+=x[{it, u}];
        }
        q.push(in);
        x[{in, u}]=x[{u, in}]=2LL*c[u]-sm;
    }
}

int main()
{
    setIO();
    cin >> n >> m;
    FOR(i, 0, n) cin >> c[i];
    FOR(i, 0, m)
    {
        int a, b; cin >> a >> b; a--; b--;
        ad[a].PB(b);
        ad[b].PB(a);
        con[i]={a, b};
    }
    if(n<m){
        cout << 0;
        return 0;
    }

    vi lf;
    FOR(i, 0, n) if(ad[i].size()==1) lf.PB(i);

    for(auto u : lf){
        q.push(u);
    }

    bfs();

    int in=-1;
    FOR(i, 0, n)
    {
        if(!v[i]){
            in=i;
        }
    }

    if(in==-1){
        FOR(i, 0, m)
        {
            cout << x[con[i]] << '\n';
        }
        return 0;
    }


}

Compilation message

pipes.cpp: In function 'void setIO(std::string)':
pipes.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11976 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct
3 Correct 8 ms 12236 KB Output is correct
4 Correct 400 ms 37104 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 6 ms 12080 KB Output is correct
7 Correct 7 ms 11980 KB Output is correct
8 Correct 7 ms 11980 KB Output is correct
9 Correct 9 ms 12236 KB Output is correct
10 Correct 8 ms 12236 KB Output is correct
11 Correct 9 ms 12236 KB Output is correct
12 Correct 9 ms 12208 KB Output is correct
13 Correct 278 ms 32140 KB Output is correct
14 Correct 349 ms 35632 KB Output is correct
15 Correct 368 ms 37148 KB Output is correct
16 Correct 301 ms 33320 KB Output is correct
17 Correct 369 ms 37152 KB Output is correct
18 Correct 377 ms 37148 KB Output is correct
19 Correct 258 ms 36904 KB Output is correct
20 Correct 7 ms 12076 KB Output is correct
21 Correct 8 ms 12236 KB Output is correct
22 Correct 375 ms 37324 KB Output is correct
23 Correct 273 ms 31916 KB Output is correct
24 Correct 389 ms 37252 KB Output is correct
25 Correct 293 ms 32964 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 11980 KB Output isn't correct
2 Incorrect 7 ms 12076 KB Output isn't correct
3 Incorrect 170 ms 29636 KB Output isn't correct
4 Correct 65 ms 23784 KB Output is correct
5 Correct 60 ms 23540 KB Output is correct
6 Correct 243 ms 59468 KB Output is correct
7 Incorrect 7 ms 12072 KB Output isn't correct
8 Incorrect 7 ms 11980 KB Output isn't correct
9 Incorrect 6 ms 11980 KB Output isn't correct
10 Correct 6 ms 11980 KB Output is correct
11 Correct 6 ms 11980 KB Output is correct
12 Correct 7 ms 12084 KB Output is correct
13 Correct 6 ms 12108 KB Output is correct
14 Incorrect 7 ms 12076 KB Output isn't correct
15 Incorrect 7 ms 12108 KB Output isn't correct
16 Incorrect 8 ms 12236 KB Output isn't correct
17 Incorrect 8 ms 12212 KB Output isn't correct
18 Correct 7 ms 12080 KB Output is correct
19 Correct 7 ms 12084 KB Output is correct
20 Correct 7 ms 12108 KB Output is correct
21 Correct 8 ms 12236 KB Output is correct
22 Incorrect 8 ms 12236 KB Output isn't correct
23 Incorrect 106 ms 25352 KB Output isn't correct
24 Incorrect 173 ms 29976 KB Output isn't correct
25 Incorrect 174 ms 29620 KB Output isn't correct
26 Correct 62 ms 23748 KB Output is correct
27 Correct 60 ms 23692 KB Output is correct
28 Correct 64 ms 24200 KB Output is correct
29 Correct 198 ms 50336 KB Output is correct
30 Incorrect 143 ms 30260 KB Output isn't correct
31 Incorrect 85 ms 25468 KB Output isn't correct
32 Incorrect 273 ms 34496 KB Output isn't correct
33 Incorrect 159 ms 29612 KB Output isn't correct
34 Correct 64 ms 23852 KB Output is correct
35 Correct 60 ms 23708 KB Output is correct
36 Correct 61 ms 23824 KB Output is correct
37 Correct 245 ms 59460 KB Output is correct
38 Incorrect 154 ms 30668 KB Output isn't correct
39 Incorrect 307 ms 35280 KB Output isn't correct
40 Incorrect 181 ms 30560 KB Output isn't correct
41 Incorrect 87 ms 25412 KB Output isn't correct
42 Correct 61 ms 23704 KB Output is correct
43 Correct 65 ms 23804 KB Output is correct
44 Correct 67 ms 23504 KB Output is correct
45 Correct 202 ms 53148 KB Output is correct
46 Incorrect 151 ms 31264 KB Output isn't correct
47 Incorrect 173 ms 30332 KB Output isn't correct
48 Incorrect 93 ms 25928 KB Output isn't correct
49 Incorrect 263 ms 33408 KB Output isn't correct
50 Correct 62 ms 23748 KB Output is correct
51 Correct 65 ms 23748 KB Output is correct
52 Correct 60 ms 23524 KB Output is correct
53 Correct 207 ms 54340 KB Output is correct
54 Incorrect 162 ms 31540 KB Output isn't correct