답안 #58595 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58595	2018-07-18T11:15:50 Z	Batrr	Pipes (BOI13_pipes)	C++14	74.0741 / 100	506 ms	68564 KB

pipes

#include <bits/stdc++.h>
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
*/
#define ll long long                   
#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 
#define IOS ios_base::sync_with_stdio(0);

using namespace std;                    

const ll maxn=5e5+123,inf=1e18,mod=1e9+7,N=360360,LOG=20;
vector< pair<int,int> >g[maxn],G[maxn],path;
int n,m,cnt[maxn],ans[maxn],a[maxn],mm;
bitset<maxn>used;
void dfs(int v,int st){
    used[v]=1;
    for(int i=0;i<G[v].size();i++){
        int to=G[v][i].f;
        if(to==st)
            path.pb(G[v][i]);
        if(!used[to]){
            path.pb(G[v][i]);
            dfs(to,st);
        }
    }
}
int main(){
    #ifdef LOCAL
        freopen ("test.in", "r", stdin);
    #endif                                     
    IOS
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++){
        int v,u;
        cin>>v>>u; 
        g[v].pb({u,i});
        g[u].pb({v,i});
    }
    queue<int>q;
    for(int i=1;i<=n;i++){
        cnt[i]=g[i].size();
        if(cnt[i]==1)
            q.push(i);
    }
    while(!q.empty()){
        int v=q.front();
        q.pop();
        used[v]=1;
        for(auto to:g[v])
            if(!used[to.f]){
                cnt[to.f]--;
                if(cnt[to.f]==1)
                    q.push(to.f);
                ans[to.s]=a[v]*2;
                a[to.f]-=a[v];
            }
    }
    mm=0;
    for(int v=1;v<=n;v++){
        if(used[v])
            continue;
        for(auto to:g[v])
            if(!used[to.f]){
                mm++;
                G[v].pb(to);
            }
            
    }
    for(int i=1;i<=n;i++)
        if(!used[i] && G[i].size()!=2)
            m=-1;
    if( n==used.count()){
        for(int i=1;i<=m;i++)
            cout<<ans[i]<<endl;
        return 0;
    }
    if( (n-used.count())%2==0 || mm!=n-used.count())
        cout<<0,exit(0);
    for(int i=1;i<=n;i++)
        if(!used[i]){
            dfs(i,i);
            if( (n-used.count())!=0 )
                cout<<0,exit(0);
            ll x=0;
            for(int i=0;i<path.size();i++){
                if(i%2==0)          
                    x+=a[path[i].f];
                else
                    x-=a[path[i].f];    
            }                           
            a[path[path.size()-1].f]-=x;
            a[path[0].f]-=x;
            for(int i=1;i<path.size();i++){
                a[path[i].f]-=a[path[i-1].f];
                a[path[i-1].f]-=a[path[i-1].f];
            }
            for(int i=1;i<=m;i++)
                cout<<ans[i]<<endl;
            break;
        }
        
}

Compilation message

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<G[v].size();i++){
                 ~^~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:79:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if( n==used.count()){
         ~^~~~~~~~~~~~~~
pipes.cpp:84:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if( (n-used.count())%2==0 || mm!=n-used.count())
                                  ~~^~~~~~~~~~~~~~~~
pipes.cpp:92:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<path.size();i++){
                         ~^~~~~~~~~~~~
pipes.cpp:100:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=1;i<path.size();i++){
                         ~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	23 ms	23912 KB	Output is correct
3	Correct	30 ms	24120 KB	Output is correct
4	Correct	236 ms	31184 KB	Output is correct
5	Correct	24 ms	31184 KB	Output is correct
6	Correct	23 ms	31184 KB	Output is correct
7	Correct	25 ms	31184 KB	Output is correct
8	Correct	23 ms	31184 KB	Output is correct
9	Correct	25 ms	31184 KB	Output is correct
10	Correct	25 ms	31184 KB	Output is correct
11	Correct	27 ms	31184 KB	Output is correct
12	Correct	25 ms	31184 KB	Output is correct
13	Correct	258 ms	31704 KB	Output is correct
14	Correct	293 ms	33764 KB	Output is correct
15	Correct	296 ms	35596 KB	Output is correct
16	Correct	227 ms	36220 KB	Output is correct
17	Correct	255 ms	38520 KB	Output is correct
18	Correct	256 ms	40212 KB	Output is correct
19	Correct	241 ms	41016 KB	Output is correct
20	Correct	25 ms	41016 KB	Output is correct
21	Correct	26 ms	41016 KB	Output is correct
22	Correct	254 ms	43268 KB	Output is correct
23	Correct	253 ms	43532 KB	Output is correct
24	Correct	249 ms	46104 KB	Output is correct
25	Correct	232 ms	46428 KB	Output is correct

Subtask #2
44.0740740741 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	25 ms	46428 KB	Output isn't correct
2	Incorrect	25 ms	46428 KB	Output isn't correct
3	Correct	93 ms	48228 KB	Output is correct
4	Correct	97 ms	49380 KB	Output is correct
5	Correct	100 ms	49380 KB	Output is correct
6	Correct	393 ms	68380 KB	Output is correct
7	Incorrect	25 ms	68380 KB	Output isn't correct
8	Incorrect	26 ms	68380 KB	Output isn't correct
9	Correct	26 ms	68380 KB	Output is correct
10	Correct	24 ms	68380 KB	Output is correct
11	Correct	25 ms	68380 KB	Output is correct
12	Correct	26 ms	68380 KB	Output is correct
13	Correct	22 ms	68380 KB	Output is correct
14	Incorrect	29 ms	68380 KB	Output isn't correct
15	Incorrect	30 ms	68380 KB	Output isn't correct
16	Incorrect	22 ms	68380 KB	Output isn't correct
17	Correct	30 ms	68380 KB	Output is correct
18	Correct	25 ms	68380 KB	Output is correct
19	Correct	24 ms	68380 KB	Output is correct
20	Correct	24 ms	68380 KB	Output is correct
21	Correct	23 ms	68380 KB	Output is correct
22	Incorrect	22 ms	68380 KB	Output isn't correct
23	Incorrect	87 ms	68380 KB	Output isn't correct
24	Incorrect	106 ms	68380 KB	Output isn't correct
25	Correct	107 ms	68380 KB	Output is correct
26	Correct	168 ms	68380 KB	Output is correct
27	Correct	115 ms	68380 KB	Output is correct
28	Correct	174 ms	68380 KB	Output is correct
29	Correct	506 ms	68380 KB	Output is correct
30	Incorrect	128 ms	68380 KB	Output isn't correct
31	Incorrect	127 ms	68380 KB	Output isn't correct
32	Incorrect	135 ms	68380 KB	Output isn't correct
33	Correct	133 ms	68380 KB	Output is correct
34	Correct	126 ms	68380 KB	Output is correct
35	Correct	173 ms	68380 KB	Output is correct
36	Correct	125 ms	68380 KB	Output is correct
37	Correct	429 ms	68564 KB	Output is correct
38	Incorrect	136 ms	68564 KB	Output isn't correct
39	Incorrect	109 ms	68564 KB	Output isn't correct
40	Incorrect	145 ms	68564 KB	Output isn't correct
41	Correct	134 ms	68564 KB	Output is correct
42	Correct	140 ms	68564 KB	Output is correct
43	Correct	148 ms	68564 KB	Output is correct
44	Correct	127 ms	68564 KB	Output is correct
45	Correct	330 ms	68564 KB	Output is correct
46	Incorrect	132 ms	68564 KB	Output isn't correct
47	Incorrect	102 ms	68564 KB	Output isn't correct
48	Incorrect	112 ms	68564 KB	Output isn't correct
49	Correct	103 ms	68564 KB	Output is correct
50	Correct	167 ms	68564 KB	Output is correct
51	Correct	112 ms	68564 KB	Output is correct
52	Correct	115 ms	68564 KB	Output is correct
53	Correct	289 ms	68564 KB	Output is correct
54	Incorrect	107 ms	68564 KB	Output isn't correct

답안 #58595

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 44.0740740741 / 70.0

Subtask #1
30.0 / 30.0

Subtask #2
44.0740740741 / 70.0