Submission #1149255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149255		12345678	Tug of War (BOI15_tug)	C++20	0 / 100	15 ms	5448 KiB

tug

#include <bits/stdc++.h>

using namespace std;

const int nx=6e4+5;

int n, k, l[nx], r[nx], s[nx], vs[nx], f;
set<int> deg[nx];

void solve(int x, int idx)
{
    cout<<"debug "<<x<<' '<<idx<<'\n';
    if (l[x]==idx)
    {
        deg[r[x]].erase(idx);
        if (deg[r[x]].empty()) f=1;
        else if (deg[r[x]].size()==1) solve(*deg[r[x]].begin(), r[x]);
    }
    else
    {
        deg[l[x]].erase(idx);
        if (deg[l[x]].empty()) f=1;
        else if (deg[l[x]].size()==1) solve(*deg[l[x]].begin(), l[x]);
    }
}
int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=2*n; i++) cin>>l[i]>>r[i]>>s[i], r[i]+=n, deg[l[i]].insert(i), deg[r[i]].insert(i);
    for (int i=1; i<=2*n; i++) if (deg[i].empty()) return cout<<"NO", 0;
    for (int i=1; i<=2*n; i++) if (deg[i].size()==1&&!f) solve(*deg[i].begin(), i);
    if (f) cout<<"NO";
    else cout<<"YES"; 
}

/*
2 20
1 1 1
1 2 4
2 2 1
2 1 4

*/

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 23
• Subtask 4: 0 / 29