टेक्स्ट की तुलना करें

दो टेक्स्ट फ़ाइलों के बीच अंतर ढूंढें

रियल-टाइम एडिटर
अपरिवर्तित संक्षिप्त करें
लाइन रैप बंद
लेआउट
परिवर्तन हाइलाइट करें
सिंटैक्स हाइलाइटिंग

Untitled diff

बनाया गया Diff कभी समाप्त नहीं होता
43 हटाए गए
157 लाइनें
32 जोड़े गए
145 लाइनें
#include <cstdio>
#include<bits/stdc++.h>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#define maxn 600009
using namespace std;
using namespace std;
int UU[maxn], VV[maxn], WW[maxn], q[maxn];
const int maxn= 600100;
using namespace std;
int a[maxn], b[maxn], c[maxn], q[maxn];
typedef struct
typedef struct
{
{
int l,r;
int l,r;
}node;
}node1;
node seg[maxn];
node1 seg[maxn];
typedef struct
typedef struct
{
{
int u,v,w,id;
int u,v,w,id;
}node1;
}node2;
node1 edge[maxn];
node2 edge[maxn];
bool cmp(node1 x,node1 y)
bool cmp(node2 x,node2 y)
{
{
return x.w<y.w;
return x.w<y.w;
}
}
int p[maxn];
int p[maxn];
int findset(int x)
int findset(int x)
{
{
return x==p[x]?x:p[x]=findset(p[x]);
return x==p[x]?x:p[x]=findset(p[x]);
}
}
void unionset(int x,int y)
void unionset(int x,int y)
{
{
p[findset(x)]=findset(y);
p[findset(x)]=findset(y);
}
}
int vis[maxn];
int vis[maxn];
bool wa[maxn];
bool wa[maxn];
set<int>st;
set<int>st;
struct Edge
struct Edge
{
{
int to,id;
int to,id;
};
};
vector<Edge>G[maxn];
vector<Edge>G[maxn];
int type[maxn];
int type[maxn];
map<int, int>mp;
map<int, int>mp;

vector< vector<int> > V[maxn];
vector< vector<int> > V[maxn];
vector<int>tmp[maxn], cr;
vector<int>tmp[maxn], cr;
vector<int>buf;
vector<int>buf;
bool NO[maxn];
bool NO[maxn];



int fdset(int x){
int fdset(int x){
return q[x] == x ? x : q[x] = fdset(q[x]);
return q[x] == x ? x : q[x] = fdset(q[x]);
}
}


void unset(int x, int y){
void unset(int x, int y){
q[fdset(x)] = fdset(y);
q[fdset(x)] = fdset(y);
}
}


void doit(vector <int> &G){
void doit(vector <int> &G){
cr.clear();
cr.clear();
int lb = G[0];
int lb = G[0];
for(int j = 1; j < (int)G.size(); j++){
for(int j = 1; j < (int)G.size(); j++){
int u = UU[G[j]];
int u = a[G[j]], v = b[G[j]];
int v = VV[G[j]];
u = findset(u);v = findset(v);
u = findset(u);
v = findset(v);
if(fdset(u) == fdset(v)){
if(fdset(u) == fdset(v)){
NO[lb] = 1;
NO[lb] = 1;
}
}
unset(u, v);
unset(u, v);
cr.push_back(u);
cr.push_back(u);cr.push_back(v);
cr.push_back(v);
if(NO[lb])break;
if(NO[lb])
break;
}
}
for(auto x: cr)
for(auto x: cr)q[x] = x;
q[x] = x;
}
}


void check(int x){
void check(int x){
for(int i = 0; i < (int)V[x].size(); i++){
for(int i = 0; i < (int)V[x].size(); i++){
doit(V[x][i]);
doit(V[x][i]);
}
}
}
}


int main()
int main()
{
{
int n,m;
int n,m;
scanf("%d%d",&n,&m);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int i=1;i<=n;i++){
p[i]=i;
p[i]=i;q[i] = i;
q[i] = i;
}
}
for(int i=0;i<m;i++)
for(int i=0;i<m;i++)
{
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
UU[i + 1] = edge[i].u;
a[i+1] = edge[i].u;
VV[i + 1] = edge[i].v;
b[i+1] = edge[i].v;
WW[i + 1] = edge[i].w;
c[i+1] = edge[i].w;
edge[i].id=i+1;
edge[i].id=i+1;
}
}
sort(edge,edge+m,cmp);
sort(edge,edge+m,cmp);
int cur=0,tot=0;
int cur=0,tot=0;
while(cur<m)
while(cur<m)
{
{
seg[tot].l=cur;
seg[tot].l=cur;
while(cur+1<m&&edge[cur].w==edge[cur+1].w)
while(cur+1<m&&edge[cur].w==edge[cur+1].w)
cur++;
cur++;
seg[tot].r=cur;
seg[tot].r=cur;
mp[edge[cur].w] = tot;
mp[edge[cur].w] = tot;
cur++;tot++;
cur++;tot++;
}
}
int Q;
int q;
scanf("%d", &Q);
scanf("%d", &q);
for(int i = 1; i <= Q; i++){
for(int i = 1; i <= q; i++){
buf.clear();
buf.clear();buf.push_back(i);
buf.push_back(i);
cr.clear();
cr.clear();
int num;
int num;
scanf("%d", &num);
scanf("%d", &num);
for(int j = 0; j < num; j++){
for(int j = 0; j < num; j++){
int x;
int x;
scanf("%d", &x);
scanf("%d", &x);
int w = mp[WW[x]];
int w = mp[c[x]];
if((int)tmp[w].size() == 0){
if((int)tmp[w].size() == 0){
tmp[w].push_back(i);
tmp[w].push_back(i);
tmp[w].push_back(x);
tmp[w].push_back(x);
cr.push_back(w);
cr.push_back(w);
}
}
else{
else{
tmp[w].push_back(x);
tmp[w].push_back(x);
}
}
buf.push_back(x);
buf.push_back(x);
}
}
for(auto x: cr){
for(auto x: cr){
V[x].push_back(tmp[x]);
V[x].push_back(tmp[x]);
tmp[x].clear();
tmp[x].clear();
}
}
doit(buf);
doit(buf);
}
}
//cout << tot << endl;
for(int i=0;i<tot;i++)
for(int i=0;i<tot;i++)
{
{
check(i);
check(i);
for(int j = seg[i].l; j <= seg[i].r; j++){
for(int j = seg[i].l; j <= seg[i].r; j++){
unionset(edge[j].u, edge[j].v);
unionset(edge[j].u, edge[j].v);
}
}
}
}
for(int i = 1; i <= Q; i++)
for(int i = 1; i <= q; i++)
if(NO[i])
{
if(NO[i]){
puts("NO");
puts("NO");
else
}
else{
puts("YES");
puts("YES");
}
}
return 0;
return 0;
}
}
सेव किए गए Diffs