# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
411540 | Ruxandra985 | Graph (BOI20_graph) | C++14 | 103 ms | 10280 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
double sol[DIMN];
int f[DIMN] , f2[DIMN];
vector <pair <int , int> > v[DIMN];
vector <int> taken;
pair <int , int> cod[DIMN];
deque <int> dq;
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , m , i , a , y , z , found , nod , vecin , tip , mini , poz , sum;
double x;
fscanf (fin,"%d%d",&n,&m);
for (i = 1 ; i <= m ; i++){
fscanf (fin,"%d%d%d",&a,&y,&z);
v[a].push_back(make_pair(y , z));
v[y].push_back(make_pair(a , z));
}
for (int j = 1 ; j <= n ; j++){
if (f2[j])
continue;
cod[j] = make_pair(0 , 1);
dq.push_back(j);
f[j] = 1;
found = 0;
taken.clear();
while (!dq.empty() && !found){
nod = dq.front();
dq.pop_front();
taken.push_back(nod);
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
tip = v[nod][i].second;
if (!f[vecin]){
dq.push_back(vecin);
f[vecin] = 1;
cod[vecin] = make_pair(tip - cod[nod].first , -cod[nod].second);
}
else {
/// momentul sa vezi daca relatiile sunt echivalente, contradictorii
/// sau daca sau solutia x
if (cod[vecin] == make_pair(tip - cod[nod].first , -cod[nod].second))
continue; /// echivalent
if (cod[vecin].second == -cod[nod].second && cod[vecin].first != tip - cod[nod].first){
fprintf (fout,"NO"); /// contradictorii
return 0;
}
if (cod[vecin].second != -cod[nod].second){
if (cod[vecin].second == 1){
x = 1.0 * (tip - cod[nod].first - cod[vecin].first) / 2;
found = 1;
break; /// ai aflat x
}
else {
x = 1.0 * (cod[vecin].first - tip + cod[nod].first) / 2;
found = 1;
break;
}
}
}
}
}
if (!found){
mini = 2000000000;
poz = -3;
for (i = -20 ; i <= 20 ; i++){
sum = 0;
for (int k = 0 ; k < taken.size() ; k++){
nod = taken[k];
sum = sum + max(cod[nod].first + cod[nod].second * i , - (cod[nod].first + cod[nod].second * i ));
}
if (sum < mini){
mini = sum;
poz = i;
}
}
x = poz;
found = 1;
}
dq.clear();
dq.push_back(j);
f2[j] = 2;
sol[j] = x;
while (!dq.empty()){
nod = dq.front();
dq.pop_front();
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i].first;
tip = v[nod][i].second;
if (f2[vecin] != 2){
dq.push_back(vecin);
f2[vecin] = 2;
sol[vecin] = tip - sol[nod];
}
else {
if (sol[vecin] != tip - sol[nod]){
fprintf (fout,"NO");
return 0;
}
}
}
}
}
cout << "YES\n";
for (i = 1 ; i <= n ; i++){
cout << sol[i] << " ";
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |