| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 409501 |
2021-05-21T00:35:26 Z |
rqi |
Toy Train (IOI17_train) |
C++14 |
|
896 ms |
1860 KB |
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
const int MOD = 1e9+7;
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define bk back()
#define all(x) begin(x), end(x)
const int mx = 5005;
int n, m;
vi a, r, u, v;
vi adj[mx];
vi radj[mx];
int to_in[mx];
int to_out[mx];
bool visited[mx];
vi order;
void dfs1(int node){
if(a[node] == 0 || r[node] == 1) return;
for(auto u: adj[node]){
if(!visited[u]){
visited[u] = 1;
dfs1(u);
}
}
order.pb(node);
}
vector<vi> comps;
vi comp;
void dfs2(int node){
if(a[node] == 0 || r[node] == 1) return;
comp.pb(node);
for(auto u: radj[node]){
if(!visited[u]){
visited[u] = 1;
dfs2(u);
}
}
}
void reduceAStrong(){
//create new adj, remove self edges for AN
for(int i = 0; i < n; i++){
visited[i] = 0;
}
for(int i = 0; i < n; i++){
if(!visited[i]){
visited[i] = 1;
dfs1(i);
}
}
for(int i = 0; i < n; i++){
visited[i] = 0;
}
reverse(all(order));
for(auto u: order){
if(!visited[u]){
comp.clear();
visited[u] = 1;
dfs2(u);
comps.pb(comp);
}
}
for(int i = 0; i < n; i++){
adj[i].clear();
radj[i].clear();
}
for(auto COMP: comps){
// cout << "COMP: ";
// for(auto u: COMP){
// cout << u << " ";
// }
// cout << "\n";
for(int i = 0; i < sz(COMP); i++){
to_in[COMP[i]] = COMP[0];
to_out[COMP[i]] = COMP.bk;
if(i+1 < sz(COMP)){
adj[COMP[i]].pb(COMP[i+1]);
}
}
}
for(int i = 0; i < m; i++){
int A = u[i];
int B = v[i];
if(a[A] == 1 && r[A] == 0){
A = to_out[A];
}
if(a[B] == 1 && r[B] == 0){
B = to_in[B];
}
if((a[A] == 1 && r[A] == 0) && (a[B] == 1 && r[B] == 0) && to_in[A] == to_in[B]){ //remove self edge
continue;
}
adj[A].pb(B);
}
for(int i = 0; i < n; i++){
for(auto u: adj[i]){
radj[u].pb(i);
}
}
}
array<bool, mx> dp;
array<bool, mx> ndp;
bool bad[mx];
bool forced[mx];
int cur_deg[mx]; //number of neighbors that can be forced into a good C
int bad_cur_deg[mx];
queue<int> to_unForce;
void iForce(int node){
for(auto u: radj[node]){
if(forced[u]) continue;
if(a[u] == 1){
cur_deg[u]++;
if(cur_deg[u] == sz(adj[u])){
forced[u] = 1;
to_unForce.push(u);
}
}
else{
forced[u] = 1;
to_unForce.push(u);
}
}
}
void initForce(){
for(int i = 0; i < n; i++){
if(r[i] == 1){
if(!forced[i]){
forced[i] = 1;
to_unForce.push(i);
}
}
}
while(sz(to_unForce)){
int node = to_unForce.front();
to_unForce.pop();
iForce(node);
}
for(int i = 0; i < n; i++){
if(forced[i]){
cur_deg[i] = 0;
for(auto u: adj[i]){
if(forced[u]){
cur_deg[i]++;
}
}
}
}
}
queue<int> q;
void unForce(int node){
assert(forced[node] == 0);
for(auto u: radj[node]){
if(forced[u]){
cur_deg[u]--;
if(cur_deg[u] == 0){
forced[u] = 0;
to_unForce.push(u);
if(!bad[u] && a[u] == 1){ //second condition unnecessary
bad[u] = 1;
q.push(u);
}
}
}
}
}
vi who_wins(vi _a, vi _r, vi _u, vi _v) {
a = _a;
r = _r;
u = _u;
v = _v;
n = sz(a);
m = sz(u);
for(int i = 0; i < m; i++){
adj[u[i]].pb(v[i]);
radj[v[i]].pb(u[i]);
}
initForce();
for(int i = 0; i < n; i++){
dp[i] = 1;
if(r[i] == 1) dp[i] = 0;
}
for(int rep = 0; rep < mx; rep++){
for(int i = 0; i < n; i++){
ndp[i] = 0;
}
for(int i = 0; i < n; i++){
if(r[i] == 1) continue;
if(a[i] == 1){
ndp[i] = 1;
for(auto u: adj[i]){
if(dp[u] == 0) ndp[i] = 0;
}
}
else{
ndp[i] = 0;
for(auto u: adj[i]){
if(dp[u] == 1) ndp[i] = 1;
}
}
}
swap(dp, ndp);
}
for(int i = 0; i < n; i++){
bad_cur_deg[i] = sz(adj[i]);
if(dp[i] == 1){
q.push(i);
bad[i] = 1;
//cout << "initial bad: " << i << "\n";
}
}
while(true){
while(sz(to_unForce)){
int node = to_unForce.front();
to_unForce.pop();
unForce(node);
}
if(sz(q) == 0) break;
int node = q.front();
q.pop();
for(auto u: radj[node]){
if(bad[u]) continue;
if(a[u] == 1){
bad_cur_deg[u]--;
if(bad_cur_deg[u] == 0){
bad[u] = 1;
q.push(u);
}
}
else{
bad[u] = 1;
q.push(u);
}
}
forced[node] = 0;
to_unForce.push(node);
}
vi ans(n, 0);
for(int i = 0; i < n; i++){
if(!bad[i]){
ans[i] = 1;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
1348 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
460 KB |
Output is correct |
| 2 |
Correct |
41 ms |
560 KB |
Output is correct |
| 3 |
Correct |
41 ms |
460 KB |
Output is correct |
| 4 |
Incorrect |
41 ms |
460 KB |
3rd lines differ - on the 4th token, expected: '0', found: '1' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
368 ms |
1840 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
1560 KB |
Output is correct |
| 2 |
Correct |
525 ms |
1672 KB |
Output is correct |
| 3 |
Correct |
813 ms |
1860 KB |
Output is correct |
| 4 |
Correct |
511 ms |
1776 KB |
Output is correct |
| 5 |
Correct |
718 ms |
1776 KB |
Output is correct |
| 6 |
Correct |
551 ms |
1752 KB |
Output is correct |
| 7 |
Correct |
581 ms |
1740 KB |
Output is correct |
| 8 |
Correct |
626 ms |
1712 KB |
Output is correct |
| 9 |
Correct |
126 ms |
1612 KB |
Output is correct |
| 10 |
Correct |
201 ms |
1812 KB |
Output is correct |
| 11 |
Correct |
135 ms |
1812 KB |
Output is correct |
| 12 |
Correct |
211 ms |
1800 KB |
Output is correct |
| 13 |
Correct |
848 ms |
1784 KB |
Output is correct |
| 14 |
Correct |
598 ms |
1676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
896 ms |
1788 KB |
3rd lines differ - on the 60th token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
1348 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
