/*
nodes are spots (0-N-1:left, N - 2*N-1: right)
edges are people
weight of edge is strength
if there is only one edge in a node, remove and repeat
we are not left with cycles so all edges should have exactly two edges in it
find the possibility for each cycle
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, 2*N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=60000, INF=1000000000;
///500,000,000
int N, K, s1, s2;
bool vis[MAXN];
multiset<pair<int, int> > adj[MAXN];
multiset<pair<int, int> >::iterator it;
queue<int> emp;
main() {
//ifstream cin("test.in");
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> K;
ffi {
int a, b, d; cin >> a >> b >> d;
a--; b = b-1+N;
adj[a].insert(mp(b, d)); adj[b].insert(mp(a, d));
w<< a s b<<e;
}
ffi if (adj[i].size() == 1) emp.push(i);
while (!emp.empty()) {
int x = emp.front(); emp.pop();
it = adj[x].begin();
if (x < N) s1 += (*it).b;
else s2 += (*it).b;
adj[(*it).a].erase(adj[(*it).a].find(mp(x, (*it).b)));
if (adj[(*it).a].size() == 1) emp.push((*it).a);
adj[x].erase(it);
}
ffi if (adj[i].size() != 2 && adj[i].size() != 0) {
w<< "NO"<<e;
exit(0);
}
}
Compilation message
tug.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
3192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
3192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
5240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
3192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
