| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 408350 |
2021-05-19T07:07:20 Z |
balbit |
Toy Train (IOI17_train) |
C++14 |
|
995 ms |
1976 KB |
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
//#define BALBIT
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 5e3+5;
bool win[maxn];
int safe[maxn]; // safe edges coming out of this node
vector<int> g[maxn];
bool notcyc[maxn];
vector<int> rg[maxn];
std::vector<int> win2(std::vector<int> who, std::vector<int> station, std::vector<int> UU, std::vector<int> VV) {
int n = SZ(who);
std::vector<int> res(n);
REP(i,n) g[i].clear(), rg[i].clear();
memset(win, 0, sizeof win);
memset(safe, 0, sizeof safe);
memset(notcyc, 0, sizeof notcyc);
REP(i,SZ(UU)) {
g[UU[i]].pb(VV[i]);
rg[VV[i]].pb(UU[i]);
}
// return res;
REP(round, 3)
REP(T, n) {
if (res[T]) continue;
// T is target node
if (!station[T]) continue;
// who = 1: any is required to win
REP(i,n) safe[i] = SZ(g[i]);
memset(win, 0, sizeof win);
win[T] = 1;
queue<int> q;
REP(i,n) if (res[i] || i==T) q.push(i);
while (!q.empty() ){
int v = q.front(); q.pop();
for (int u : rg[v]) {
if (!win[u]) {
if (who[u] == 1) {
// any required
// bug(u, who[u]);
win[u] = 1; q.push(u);
}else{
-- safe[u];
if (safe[u] == 0) {
q.push(u);
win[u] = 1;
}
}
}
}
}
// continue;
bool ok = 0;
if (who[T] == 1) {
// any required
for (int u : g[T]) {
if (win[u]) {
ok = 1; break;
}
}
}else{
ok = 1;
for (int u : g[T]) {
if (!win[u]) {
// bug(T, u, win[u]);
ok=0; break;
}
}
}
// bug(T, ok);
if (ok) {
REP(i,n) {
// bug(i, win[i]);
if (win[i]) res[i] = 1;
}
}
}
return res;
}
//bitset<maxn> fren[maxn];
vector<int> love[maxn];
int nlove[maxn];
int seff[maxn][2];
bool touch[maxn][2];
std::vector<int> who_wins(std::vector<int> who, std::vector<int> station, std::vector<int> UU, std::vector<int> VV) {
int n = SZ(who);
std::vector<int> res(n);
REP(i,n) g[i].clear(), rg[i].clear();
memset(win, 0, sizeof win);
memset(safe, 0, sizeof safe);
memset(notcyc, 0, sizeof notcyc);
memset(nlove, 0, sizeof nlove);
REP(i,n) love[i].clear();
REP(i,SZ(UU)) {
g[UU[i]].pb(VV[i]);
rg[VV[i]].pb(UU[i]);
}
// return res;
{
queue<int> q;
REP(i,n) {
if (station[i]) q.push(i), notcyc[i] = 1;
else safe[i] = SZ(g[i]);
}
// create things that aren't zero-cycles
while (!q.empty() ) {
int v = q.front(); q.pop();
for (int u : rg[v]) {
if (!notcyc[u]) {
if (who[u] == 1) {
// i like stations!
notcyc[u] = 1; q.push(u);
}else{
--safe[u];
if( safe[u] == 0) {
notcyc[u] = 1; q.push(u);
}
}
}
}
}
}
REP(T, n) {
if (res[T]) continue;
// T is target node
if(!(station[T] || (notcyc[T]))) {
continue;
}
bug(T);
// who = 1: any is required to win
REP(i,n) seff[i][0] = seff[i][1] = SZ(g[i]);
memset(touch, 0, sizeof touch);
touch[T][station[T]] = 1;
vector<pii> q; q.pb({T, station[T]});
int IT = 0;
while (IT < SZ(q)){
int v = q[IT].f; bool B = q[IT].s; ++IT;
if (!touch[v][0]) {
touch[v][0] = 1; q.pb({v,0});
}
for (int u : rg[v]) {
bool he = B | station[u];
if (!touch[u][he]) {
if (who[u] == 1) {
// any required
// bug(u, who[u]);
touch[u][he] = 1; q.pb({u,he});
}else{
// -- seff[u][he];
if (--seff[u][B] <= 0) {
if (!touch[u][he]) {
q.pb({u,he});
touch[u][he] = 1;
}
}
}
}
}
}
bool ok = 0;
if (!touch[T][1]) continue;
if (who[T] == 1) {
// any required
for (int u : g[T]) {
if (touch[u][1]) {
ok = 1; break;
}
}
}else{
ok = 1;
for (int u : g[T]) {
if (!touch[u][1]) {
// bug(T, u, win[u]);
ok=0; break;
}
}
}
bug(T, ok);
touch[T][1] = ok;
if (ok)
REP(i,n){
if (touch[i][0]) {
res[i] = 1;
// bug(T,i);
}
}
}
return res;
memset(win, 0, sizeof win);
{
queue<int> q;
REP(i,n) {
if (!notcyc[i] || (who[i] == 1 && nlove[i] == 0)) {
bug(i, notcyc[i]);
q.push(i);
win[i] = 1;
}
// safe[i] = SZ(g[i]);
}
bitset<maxn> alive;
alive.set();
while (!q.empty() ) {
int v = q.front(); q.pop();
// if (win[v]) continue;
for (int u : rg[v]) {
if (!win[u]) {
if (who[u] == 0) {
// i hate stations!
win[u] = 1; q.push(u);
}
}
}
if (station[v]) {
for (int u : love[v]) {
if (!win[u])
if (who[u] == 1 && (--nlove[u] <= 0) ) {
q.push(u); win[u] = 1;
}
}
}
}
}
REP(i,n) res[i] = !win[i];
return res;
}
#ifdef BALBIT
signed main() {
int n,m; cin>>n>>m;
REP(ffff, 1000) {
vector<int >a,r;
REP(i,n) a.pb(rand()%2);
REP(i,n) {
r.pb(rand()%2);
if (r.back()) a[i] = 1;
}
vector<int> u,v;
REP(i,m) {
u.pb(rand()%n);
if (i<n) u[i] = i;
v.pb(rand()%n);
}
vector<int> r1 = win2(a,r,u,v);
vector<int> r2 = who_wins(a,r,u,v);
if (r1 != r2) {
for (int x : r1) cout<<x<<' ';
cout<<endl;
for (int x : r2) cout<<x<<' ';
cout<<endl;
cout<<"A"<<endl;
for (int x : a) cout<<x<<' ';
cout<<endl;
for (int x : r) cout<<x<<' ';
cout<<endl;
for (int x : u) cout<<x<<' ';
cout<<endl;
for (int x : v) cout<<x<<' ';
cout<<endl;
assert(0);
}
}
}
#endif
/*
2 4
0 1
1 0
0 0
0 1
1 0
1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
1248 KB |
3rd lines differ - on the 26th token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
588 KB |
3rd lines differ - on the 2nd token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
963 ms |
1840 KB |
Output is correct |
| 2 |
Correct |
870 ms |
1836 KB |
Output is correct |
| 3 |
Correct |
995 ms |
1976 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1916 KB |
Output is correct |
| 5 |
Correct |
421 ms |
1764 KB |
Output is correct |
| 6 |
Correct |
826 ms |
1688 KB |
Output is correct |
| 7 |
Correct |
15 ms |
1776 KB |
Output is correct |
| 8 |
Correct |
13 ms |
1644 KB |
Output is correct |
| 9 |
Correct |
11 ms |
1452 KB |
Output is correct |
| 10 |
Correct |
14 ms |
1616 KB |
Output is correct |
| 11 |
Correct |
27 ms |
1648 KB |
Output is correct |
| 12 |
Correct |
10 ms |
1484 KB |
Output is correct |
| 13 |
Correct |
10 ms |
1740 KB |
Output is correct |
| 14 |
Correct |
12 ms |
1716 KB |
Output is correct |
| 15 |
Correct |
12 ms |
1740 KB |
Output is correct |
| 16 |
Correct |
15 ms |
1740 KB |
Output is correct |
| 17 |
Correct |
28 ms |
1740 KB |
Output is correct |
| 18 |
Correct |
784 ms |
1740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
1476 KB |
3rd lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1580 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1776 KB |
Output is correct |
| 3 |
Correct |
581 ms |
1616 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1612 KB |
Output is correct |
| 5 |
Correct |
2 ms |
716 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1100 KB |
Output is correct |
| 7 |
Correct |
9 ms |
1188 KB |
Output is correct |
| 8 |
Correct |
32 ms |
1228 KB |
Output is correct |
| 9 |
Correct |
24 ms |
1312 KB |
Output is correct |
| 10 |
Correct |
3 ms |
896 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
1248 KB |
3rd lines differ - on the 26th token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
