oj.uz

답안 #670447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670447 2022-12-09T06:36:34 Z jamezzz Graph (BOI20_graph) C++17
0 / 100
 2 ms 2644 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define sf scanf
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;

#define maxn 100005

int n,m;
double ans[maxn];
ii val[maxn];
vector<int> sub;
vector<ii> AL[maxn];
vector<iii> back;

void dfs(int u,int p){
    sub.pb(u);
	for(auto[v,w]:AL[u]){
	    if(v==p)continue;
	    if(val[v].fi!=0)back.pb({u,v,w});
	    else{
	        val[v].fi=-val[u].fi;
	        val[v].se=w-val[u].se;
	        dfs(v,u);
	    }
	}
}

int main(){
	sf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		int a,b,c;sf("%d%d%d",&a,&b,&c);
		AL[a].pb({b,c});
		AL[b].pb({a,c});
	}
	for(int i=1;i<=n;++i){
		if(val[i].fi!=0)continue;
		back.clear();
		sub.clear();
		val[i]={1,0};
		dfs(i,-1);
		if(back.size()==0){
		    vector<double> xs;
		    for(int i:sub){
		        xs.pb((double)val[i].se/val[i].fi);
		    }
		    sort(all(xs));
		    double x=xs[xs.size()/2];
		    for(int i:sub){
		        ans[i]=x*val[i].fi+val[i].se;
		    }
		}
		else{
		    double x=0;
		    bool done=false,pos=true;
		    for(auto[a,b,c]:back){
    		    auto[a1,a2]=val[a];
    		    auto[b1,b2]=val[b];
    		    if(done){
    		        if(a1*x+a2+b1*x+b2!=c){
    		            pos=false;
    		            break;
    		        }
    		    }
    		    else{
    		        if(a1+b1==0){
    		            if(a2+b2!=c){
    		                pos=false;
    		                break;
    		            }
    		        }
    		        else{
    		            x=(double)(c-a2-b2)/(a1+b1);
    		            done=true;
    		        }
    		    }
		    }
		    if(!pos){
		        pf("NO\n");
		        exit(0);
		    }
		    for(int i:sub){
		        ans[i]=val[i].fi*x+val[i].se;
		    }
		}
	}
	pf("YES\n");
	for(int i=1;i<=n;++i){
	    pf("%f ",ans[i]);
	}
}

Compilation message

Graph.cpp: In function 'int main()':
Graph.cpp:36:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  sf("%d%d",&n,&m);
      |    ^
Graph.cpp:38:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   int a,b,c;sf("%d%d%d",&a,&b,&c);
      |               ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 1 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Incorrect 1 ms 2644 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 1 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Incorrect 1 ms 2644 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 1 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Incorrect 1 ms 2644 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 1 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Incorrect 1 ms 2644 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 1 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Incorrect 1 ms 2644 KB participant answer is larger than the answer of jury
7 Halted 0 ms 0 KB -