| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 99214 | eriksuenderhauf | 전선 연결 (IOI17_wiring) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "wiring.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 5e3 + 5;
const double eps = 1e-9;
vi adj[MAXN];
int deg[MAXN], cnt[MAXN];
void dfs(int u, vi& r) {
for (int v: adj[u])
{
cnt[v]--;
if (r[v] == 1 || cnt[v] != 0)
continue;
dfs(v, r);
}
}
vi who_wins(vi a, vi r, vi u, vi v) {
int n = a.size(), m = u.size();
for (int i = 0; i < m; i++)
adj[v[i]].pb(u[i]), deg[u[i]]++;
vi ans;
for (int i = 0; i < n; i++) ans.pb(1);
while (1)
{
for (int i = 0; i < n; i++)
cnt[i] = a[i] == 1 ? 1 : deg[i];
for (int i = 0; i < n; i++)
if (r[i] == 1 && ans[i] == 1)
dfs(i, r);
int fl = 0;
for (int i = 0; i < n; i++)
if (r[i] == 1 && ans[i] == 1 && cnt[i] > 0)
ans[i] = 0, fl = 1;
if (fl == 0)
break;
}
for (int i = 0; i < n; i++)
ans[i] &= cnt[i] <= 0;
return ans;
}