This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
vector<vector<int>> adj,adjr;
vector<bool> vis;
vector<int> ord;
vector<int> scc;
vector<int> l,r,S;
bool comp(int a,int b){
return S[a]<S[b];
}
void dfs(int v){
vis[v]=true;
for(auto u:adj[v]){
if(vis[u]) continue;
dfs(u);
}
ord.push_back(v);
}
void dfs2(int v,int id){
scc[v]=id;
vis[v]=true;
for(auto u:adjr[v]){
if(vis[u]) continue;
dfs2(u,id);
}
}
void addedge(int a,int b){
adj[a].push_back(b);
adjr[b].push_back(a);
}
int main() {_
auto st=clock();
int n,k;
cin>>n>>k;
l.resize(2*n);
r.resize(2*n);
S.resize(2*n);
int all=0;
vector<vector<int>> ls(n),rs(n);
for(int i=0;i<2*n;i++){
cin>>l[i]>>r[i]>>S[i];
l[i]--;
r[i]--;
ls[l[i]].push_back(i);
rs[r[i]].push_back(i);
all+=S[i];
}
adj.resize(4*n),adjr.resize(4*n);
vis.resize(4*n);
scc.resize(4*n);
for(int i=0;i<n;i++){
if(ls[i].empty() or rs[i].empty()){
cout<<"NO"<<'\n';
return 0;
}
for(auto a:ls[i]){
for(auto b:ls[i]){
if(a!=b){
addedge(2*a,2*b+1);
}
}
}
for(auto a:rs[i]){
for(auto b:rs[i]){
if(a!=b){
addedge(2*a+1,2*b);
}
}
}
}
vector<int> ord1(4*n);
for(int i=0;i<4*n;i++){
ord1[i]=4*n-1-i;
}
sort(all(ord1),comp);
mt19937 rng(time(NULL));
while(clock()-st<2.99*CLOCKS_PER_SEC){
fill(all(vis),false);
ord.clear();
for(int i=0;i<4*n;i++){
if(!vis[ord1[i]]){
dfs(ord1[i]);
}
}
shuffle(all(ord1),rng);
reverse(all(ord));
fill(all(vis),false);
int cnt=0;
for(int i=0;i<4*n;i++){
if(!vis[ord[i]]){
dfs2(ord[i],cnt++);
}
}
int sum=0;
for(int i=0;i<2*n;i++){
if(scc[i*2]==scc[i*2+1]){
cout<<"NO"<<'\n';
return 0;
}
else{
if(scc[i*2]<scc[i*2+1]){
sum+=S[i];
}
}
}
if(abs(sum-(all-sum))<=k){
cout<<"YES"<<'\n';
return 0;
}
}
cout<<"NO"<<'\n';
return 0;
}
//maybe its multiset not set
//yeeorz
//laborz
Compilation message (stderr)
tug.cpp: In function 'void setIO(std::string)':
tug.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tug.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |