#1170315 (C++23) No.3582 部分和不等式

• 問題: No.3582 部分和不等式
• ユーザー: tkdgkb
• 提出日時: 2026-07-03 23:15:24
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 6,108 bytes
• コンパイル時間: 3,096 ms
• コンパイル使用メモリ: 357,628 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-07-03 23:16:12
• 合計ジャッジ時間: 4,009 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

ファイルパターン	結果
other	AC * 10 WA * 20

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<class T>using pqg=priority_queue<T,vector<T>,greater<T>>;
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
#define sz(x) (int)x.size()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const ll INF=4e18;
const int MOD=1e9+7;
const int MOD2=998244353;
ll modpow(ll a,ll b,ll m=MOD){
    ll r=1;
    while(b){
        if(b&1)r=r*a%m;
        a=a*a%m;
        b>>=1;
    }
    return r;
}

struct DSU{
    vi p,s;
    DSU(int n){p.resize(n);s.assign(n,1);iota(all(p),0);}
    int find(int x){return p[x]==x?x:p[x]=find(p[x]);}
    bool join(int a,int b){a=find(a);b=find(b);if(a==b)return 0;if(s[a]<s[b])swap(a,b);p[b]=a;s[a]+=s[b];return 1;}
};
struct BIT{
    int n;vl b;
    BIT(int n):n(n),b(n+1){}
    void add(int i,ll v){for(;i<=n;i+=i&-i)b[i]+=v;}
    ll sum(int i){ll r=0;for(;i;i-=i&-i)r+=b[i];return r;}
};
struct LazySeg{
    int n;vl t,lz;
    LazySeg(int n):n(n),t(4*n),lz(4*n){}
    void push(int x,int l,int r){
        if(!lz[x])return;
        int m=(l+r)/2;
        t[x*2]+=(m-l+1)*lz[x];
        t[x*2+1]+=(r-m)*lz[x];
        lz[x*2]+=lz[x];
        lz[x*2+1]+=lz[x];
        lz[x]=0;
    }
    void add(int x,int l,int r,int a,int b,ll v){
        if(b<l||r<a)return;
        if(a<=l&&r<=b){t[x]+=(r-l+1)*v;lz[x]+=v;return;}
        push(x,l,r);
        int m=(l+r)/2;
        add(x*2,l,m,a,b,v);
        add(x*2+1,m+1,r,a,b,v);
        t[x]=t[x*2]+t[x*2+1];
    }
};
struct Dinic{
    struct E{int to,rev;ll cap;};
    int n;vector<vector<E>>g;vi lv,it;
    Dinic(int n):n(n),g(n),lv(n),it(n){}
    void add(int a,int b,ll c){
        g[a].push_back({b,(int)g[b].size(),c});
        g[b].push_back({a,(int)g[a].size()-1,0});
    }
    bool bfs(int s,int t){
        fill(all(lv),-1);
        queue<int>q;q.push(s);lv[s]=0;
        while(q.size()){
            int x=q.front();q.pop();
            for(auto&e:g[x])if(e.cap&&lv[e.to]<0)lv[e.to]=lv[x]+1,q.push(e.to);
        }
        return lv[t]>=0;
    }
    ll dfs(int x,int t,ll f){
        if(x==t)return f;
        for(int&i=it[x];i<sz(g[x]);i++){
            auto&e=g[x][i];
            if(e.cap&&lv[e.to]==lv[x]+1){
                ll r=dfs(e.to,t,min(f,e.cap));
                if(r){e.cap-=r;g[e.to][e.rev].cap+=r;return r;}
            }
        }
        return 0;
    }
    ll flow(int s,int t){
        ll r=0;
        while(bfs(s,t)){
            fill(all(it),0);
            while(ll f=dfs(s,t,INF))r+=f;
        }
        return r;
    }
};
vector<int> prefix(string s){
    vector<int>p(sz(s));
    rep(i,1,sz(s)){
        int j=p[i-1];
        while(j&&s[i]!=s[j])j=p[j-1];
        if(s[i]==s[j])j++;
        p[i]=j;
    }
    return p;
}
vector<int> zfunc(string s){
    int n=sz(s),l=0,r=0;
    vector<int>z(n);
    rep(i,1,n){
        if(i<=r)z[i]=min(r-i+1,z[i-l]);
        while(i+z[i]<n&&s[z[i]]==s[i+z[i]])z[i]++;
        if(i+z[i]-1>r)l=i,r=i+z[i]-1;
    }
    return z;
}
struct SAM{
    struct Node{int nxt[26],link,len;Node(){memset(nxt,-1,sizeof(nxt));link=-1;len=0;}};
    vector<Node>st;int last;
    SAM(){st.push_back(Node());last=0;}
    void add(char c){
        int cur=sz(st);st.push_back(Node());st[cur].len=st[last].len+1;
        int p=last;
        while(p!=-1&&st[p].nxt[c-'a']==-1){st[p].nxt[c-'a']=cur;p=st[p].link;}
        if(p==-1)st[cur].link=0;
        else st[cur].link=st[p].nxt[c-'a'];
        last=cur;
    }
};
struct Point{
    ld x,y;
    Point(){}
    Point(ld x,ld y):x(x),y(y){}
    Point operator-(Point p){return {x-p.x,y-p.y};}
    ld cross(Point p){return x*p.y-y*p.x;}
};
pair<ll, int> dp[1005][1005];
void solve() {
    int n, q; cin >> n >> q; 
    vector<vector<int>> S(q), T(q);
    vl M(q);
    vector<vector<int>> vs(n + 1), vt(n + 1);
    rep(i, 0, q) {
        int a, b;
        cin >> a >> b >> M[i];
        S[i].resize(a);
        rep(j, 0, a) {
            cin >> S[i][j];
            vs[S[i][j]].push_back(i);
        }
        T[i].resize(b);
        rep(j, 0, b) {
            cin >> T[i][j];
            vt[T[i][j]].push_back(i);
        }
    }
    vi active(q, 1);
    queue<int> Q;
    auto rem = [&](int idx) {
        if (!active[idx]) return;
        active[idx] = 0;
        Q.push(idx);
    };
    rep(i, 1, n + 1) {
        if (sz(vs[i]) != 1 || sz(vt[i]) != 1) {
            for (int x : vs[i]) rem(x);
            for (int x : vt[i]) rem(x);
        }
    }
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int v : S[u]) {
            auto it = find(all(vs[v]), u);
            if (it != vs[v].end()) vs[v].erase(it);

            if (vs[v].empty()) {
                for (int x : vt[v]) rem(x);
            }
        }
        for (int v : T[u]) {
            auto it = find(all(vt[v]), u);
            if (it != vt[v].end()) vt[v].erase(it);

            if (vt[v].empty()) {
                for (int x : vs[v]) rem(x);
            }
        }
    }
    vector<vector<int>> adj(q);
    rep(i, 1, n + 1) {
        if (sz(vs[i]) == 1 && sz(vt[i]) == 1) {
            int u = vs[i][0];
            int v = vt[i][0];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }
    vi vis(q, 0);
    rep(i, 0, q) {
        if (!active[i] || vis[i]) continue;
        vi comp;
        queue<int> qg;
        qg.push(i);
        vis[i] = 1;
        while (!qg.empty()) {
            int u = qg.front();
            qg.pop();
            comp.push_back(u);
            for (int v : adj[u]) {
                if (!vis[v] && active[v]) {
                    vis[v] = 1;
                    qg.push(v);
                }
            }
        }
        ll s = 0;
        for (int x : comp) {
            s += (-M[x] - 1);
        }
        if (s < 0) {
            cout << "Yes\n";
            return;
        }
    }
    cout << "No\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //int T; cin >> T; 
    //while (T--)
    solve();
}