# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
767562 |
2023-06-26T20:56:15 Z |
canadavid1 |
Graph (BOI20_graph) |
C++17 |
|
1 ms |
212 KB |
#include <bits/stdc++.h>
using namespace std;
struct Node
{
vector<pair<Node*,bool>> neigh;
int x_parity = 0; // actual value = value + x*x_parity
float value = NAN;
bool seen = false; // collect_all_vi
bool seen2 = false; // set_x
variant<float,bool> assign(float val=0,int par=1) // float - unique solution for x
{ // bool - works for any/no x
if(!isnan(value))
{
if(x_parity==par) return val == value;
// solve linear equation x * x_parity + value == x*par + val
// x * (x_parity - par) == val - value
// x = val - value / (x_parity - par)
float x = ((float) val - value) / ((float) x_parity - par);
return x;
}
value = val;
x_parity = par;
float x = NAN;
for(auto nt : neigh)
{
auto n = nt.first;
auto t = nt.second;
auto a = n->assign((1+t)-val,-par);
if(a.index()==0)
{
// unique solution for x found
if (!isnan(x) && x != get<float>(a)) return false;
x = get<float>(a);
}
else if (!get<bool>(a)) return false;
}
if(isnan(x)) return true;
return x;
}
void collect_v_i(vector<int>& v_i) // v_i in abs(x-v_i)
{
if(seen) return;
seen = true;
v_i.push_back(-value*x_parity);
for(auto nt : neigh) nt.first->collect_v_i(v_i);
}
void set_x(float x)
{
if(seen2) return;
seen2 = true;
value += x*x_parity;
for(auto nt : neigh) nt.first->set_x(x);
}
// need to decide for value of x (probably small, but uncertain)
// the total weigth is a sum of elements of type abs(v_i+x)
// collect all v_i (traversing) - x must be some -v_i. nlogn given sorting.
// binary search over larger/smaller than these and these elements, gives linear relationship
};
signed main()
{
cin.tie(nullptr)->sync_with_stdio(false);
int N,M;
cin >> N >> M;
vector<Node> nodes(N);
for(int i = 0; i < M; i++)
{
int a,b,c;
cin >> a >> b >> c;
nodes[a-1].neigh.push_back({&nodes[b-1],c>1});
nodes[b-1].neigh.push_back({&nodes[a-1],c>1});
}
for(int t = 0; t < N; t++)
{
if(!isnan(nodes[t].value)) continue; // node already seen
auto a = nodes[t].assign();
if(a.index()==0) // a is a float => x is fixed
{
float x = get<float>(a);
nodes[t].set_x(x); // recursive
}
else
{
// a is a bool.
if (!get<bool>(a))
{
cout << "NO\n";
exit(0);
} // not possible.
// need to figure out optimal value for x.
vector<int> vi;
nodes[t].collect_v_i(vi);
sort(vi.begin(),vi.end());
int x = vi[0];
int cost = 0;
for(auto i : vi) cost += (i-x);
int min_cost = cost;
int min_x = x;
for(int i = 1; i < vi.size(); i++)
{
int next_x = vi[i];
cost -= (next_x-x)*(vi.size()-i);
cost += (next_x-x)*(i);
if (min_cost > cost)
{
min_cost = cost;
min_x = x;
}
}
nodes[t].set_x(min_x);
}
}
cout << "YES\n" << nodes[0].value;
for(int i = 1; i < N; i++) cout << " " << nodes[i].value;
cout << "\n";
// assign "x" to some node
// continue traversing, getting either x+int or int-x for some edges
// if reencounter, might constrain x, set.
// repeat for all connected components
}
Compilation message
Graph.cpp: In function 'int main()':
Graph.cpp:105:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i = 1; i < vi.size(); i++)
| ~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
answer = YES |
2 |
Correct |
1 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
1 ms |
212 KB |
answer = NO |
5 |
Correct |
1 ms |
212 KB |
answer = YES |
6 |
Incorrect |
1 ms |
212 KB |
participant answer is larger than the answer of jury |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
answer = YES |
2 |
Correct |
1 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
1 ms |
212 KB |
answer = NO |
5 |
Correct |
1 ms |
212 KB |
answer = YES |
6 |
Incorrect |
1 ms |
212 KB |
participant answer is larger than the answer of jury |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
answer = YES |
2 |
Correct |
1 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
1 ms |
212 KB |
answer = NO |
5 |
Correct |
1 ms |
212 KB |
answer = YES |
6 |
Incorrect |
1 ms |
212 KB |
participant answer is larger than the answer of jury |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
answer = YES |
2 |
Correct |
1 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
1 ms |
212 KB |
answer = NO |
5 |
Correct |
1 ms |
212 KB |
answer = YES |
6 |
Incorrect |
1 ms |
212 KB |
participant answer is larger than the answer of jury |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
answer = YES |
2 |
Correct |
1 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
1 ms |
212 KB |
answer = NO |
5 |
Correct |
1 ms |
212 KB |
answer = YES |
6 |
Incorrect |
1 ms |
212 KB |
participant answer is larger than the answer of jury |
7 |
Halted |
0 ms |
0 KB |
- |