| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 581767 |
2022-06-23T05:59:40 Z |
HunterXD |
Graph (BOI20_graph) |
C++17 |
|
1 ms |
340 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double dl;
typedef pair<int,int> ii;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector <char> vc;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef pair<ll,ll> pl;
typedef double dou;
typedef vector<pl> vpl;
typedef unsigned long long ull;
typedef uint64_t i64;
typedef vector<ull> vull;
#define f first
#define s second
#define pb push_back
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define ts to_string
#define lb lower_bound
#define ub upper_bound
#define yes cout<<'Y'<<'E'<<'S'<<endl
#define no cout<<'N'<<'O'<<endl
#define nd "\n"
void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll mcm(ll a, ll b) {return (a * b) / gcd(a, b);}
bool prime(ll n) {for(int i=2; i<=sqrt(n); i++) if(n%i==0) return false; return true;}
struct compii{bool operator()(const ii &a, const ii &b){if(a.f==a.s)return a.s<b.s;return a.f>b.f;}};
bool comp(int a, int b) {return a>b;}
ll binpow(ll n, ll x){ll ans=1; while(x){if(x&1){ans*=n;}n*=n; x>>=1;} return ans;}
namespace operators {
template<typename T1, typename T2>istream& operator>>(istream& in, pair<T1, T2>& x){in >> x.first >> x.second;return in;}
template<typename T1, typename T2>ostream& operator<<(ostream& out, pair<T1, T2> x){out << x.first << " " << x.second;return out;}
template<typename T1>istream& operator>>(istream& in, vector<T1>& x) {for (auto& i : x) in >> i;return in;}
template<typename T1>ostream& operator<<(ostream& out, vector<T1>& x) {for (auto& i : x) out << i << " ";return out;}
template<typename T1, typename T2>ostream& operator<<(ostream& out, vector<pair <T1,T2>>& x) {for (auto& i : x) out << i.f << " "<<i.s;return out;}
template<typename T1, typename T2>istream& operator>>(istream& in, vector<pair <T1,T2>>& x) {for (auto& i : x) in >> i.f >>i.s;return in;}
}
using namespace operators;
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};
const int pmod = 998244353;
const int mod = 1e9+7;
const ll inf=1e18;
ll sum(ll a, ll b){
return (( (a+mod) %mod) + ((b+mod)%mod))%mod;
}
ll multi(ll a, ll b){
return (((a+mod) %mod) * ((b+mod)%mod))%mod;
}
///
dl x;
bool can = true, xfind;
vector<bool> seenDFS, seenVAL;
vector<pl> my;
vector<ll> pending;
vector<dl> val;
vector< vector<ll> > graphB, graphR;
void dfs(ll u, pl next){
pending.pb(u);
seenDFS[u] = true;
my[u] = next;
pl nextB = next;
nextB.f *= -1;
nextB.s = 1-next.s;
pl nextR = next;
nextR.f *= -1;
nextR.s = 2-next.s;
pl p1, p2;
for(auto v: graphB[u]){
if(!seenDFS[v]){
dfs(v, nextB);
}
else{
if(nextB != my[v]){
if(nextB.f == my[v].f){
can = false;
}
else{
x = (my[v].s-nextB.s)/( (dl) (nextB.f - my[v].f) );
xfind = true;
}
}
}
}
for(auto v: graphR[u]){
if(!seenDFS[v]){
dfs(v, nextR);
}
else{
if(nextR != my[v]){
if(nextR.f == my[v].f){
can = false;
}
else{
x = (my[v].s-nextR.s)/( (dl) (nextR.f - my[v].f) );
xfind = true;
}
}
}
}
}
void dfs_assign(ll u){
seenVAL[u] = true;
val[u] = (dl) (my[u].f*x + my[u].s);
for(auto v: graphB[u]){
if(!seenVAL[v]){
dfs_assign(v);
}
}
for(auto v: graphR[u]){
if(!seenVAL[v]){
dfs_assign(v);
}
}
}
dl calc_val(ll med){
dl res = 0;
for(auto u: pending){
res += abs(my[u].f*med + my[u].s);
}
return res;
}
void calc_res(ll i){
ll m = pending.size();
vector<ll> pos, neg, tod;
ll half = m/2, bestAns = m+100;
for(auto v: pending){
if(my[v].f == 1){
pos.pb(-1*my[v].s);
tod.pb(-1*my[v].s);
}
else{
neg.pb(my[v].s);
tod.pb(my[v].s);
}
}
sort(all(pos), greater<ll>());
sort(all(neg));
vector<ll>::iterator it;
ll tempAns, t1, t2;
for(auto v: tod){
t1 = 0; t2 = 0;
ll t1ini = 0, t1fini = pos.size()-1, t1med;
ll t1res = inf;
bool t1can = false;
while(t1ini <= t1fini){
t1med = (t1ini+t1fini+1)/2;
if(v >= pos[t1med]){
t1can = true;
t1res = min(t1res, t1med);
t1ini = t1med+1;
}
else{
t1fini = t1med-1;
}
}
if(t1can){
t1 = pos.size() - t1res;
}
ll t2ini = 0, t2fini = pos.size()-1, t2med;
ll t2res = -1*inf;
bool t2can = false;
while(t2ini <= t2fini){
t2med = (t2ini+t2fini+1)/2;
if(v <= neg[t2med]){
t2can = true;
t2res = max(t2res, t2med);
t2ini = t2med+1;
}
else{
t2fini = t2med-1;
}
}
if(t2can){
t2 = t2res+1;
}
tempAns = t1 + t2;
if(abs(half-tempAns) < abs(half-bestAns) ){
bestAns = v;
}
}
x = bestAns;
dfs_assign(i);
}
void solve(){
ll n, m;
cin >> n >> m;
graphB.assign(n+1, vector<ll>());
graphR.assign(n+1, vector<ll>());
val.assign(n+1, 0);
seenDFS.assign(n+1, false);
seenVAL.assign(n+1, false);
my.assign(n+1, {1, 0});
ll a[m], b[m], c[m];
for(ll i = 0; i < m; i++){
cin >> a[i] >> b[i] >> c[i];
if(c[i] == 1){
graphB[a[i]].pb(b[i]);
graphB[b[i]].pb(a[i]);
}
else{
graphR[a[i]].pb(b[i]);
graphR[b[i]].pb(a[i]);
}
}
for(ll i = 1; i <= n; i++){
if(!seenDFS[i]){
pending.clear();
xfind = false;
dfs(i, {1, 0});
if(xfind){
dfs_assign(i);
}
else{
calc_res(i);
}
}
}
if(!can){
no;
return;
}
yes;
for(ll i = 1; i <= n; i++){
cout << val[i] << " ";
}
cout << endl;
}
int main (){
setIO("");
int t = 1;
//cin >> t;
while(t-->0) solve();
return 0;
}
Compilation message
Graph.cpp: In function 'void setIO(std::string)':
Graph.cpp:35:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Graph.cpp:35:128: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
answer = YES |
| 2 |
Correct |
0 ms |
212 KB |
answer = YES |
| 3 |
Correct |
1 ms |
212 KB |
answer = YES |
| 4 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
answer = YES |
| 2 |
Correct |
0 ms |
212 KB |
answer = YES |
| 3 |
Correct |
1 ms |
212 KB |
answer = YES |
| 4 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
answer = YES |
| 2 |
Correct |
0 ms |
212 KB |
answer = YES |
| 3 |
Correct |
1 ms |
212 KB |
answer = YES |
| 4 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
answer = YES |
| 2 |
Correct |
0 ms |
212 KB |
answer = YES |
| 3 |
Correct |
1 ms |
212 KB |
answer = YES |
| 4 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
answer = YES |
| 2 |
Correct |
0 ms |
212 KB |
answer = YES |
| 3 |
Correct |
1 ms |
212 KB |
answer = YES |
| 4 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
