Submission #609586

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
609586	2022-07-27T17:41:05 Z	HediChehaidar	Toy Train (IOI17_train)	C++17	0 / 100	448 ms	2140 KB

train

#include "train.h"

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define dte  tuple<double , double , double>
using namespace std;
const int INF = 1000*1000*1000; // 1 e 9
const int MOD = 1e9 + 7;//998244353 ;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;

int n , m;
vi adj[5050];
vi rev[5050];
vi a , ch ;
vector<vi> scc;
vi no;
int idx[5050];
bool vis[5050];
bool nice[5050];
stack<int> st;
bool dfs3(int pos){
    if(nice[pos]) return true;
    if(vis[pos]) return false;
    vis[pos] = true;
    bool ans = false;
    for(auto c : adj[pos]) ans = ans || dfs3(c);
    return ans;
}
void dfs2(int pos){
    if(vis[pos]) return ;
    vis[pos] = true;
    no.pb(pos);
    idx[pos] = scc.size();
    for(auto c : rev[pos] ) dfs2(c);
}
void dfs(int pos){
    if(vis[pos]) return ;
    vis[pos] = true;
    for(auto c : adj[pos]) dfs(c);
    st.push(pos);
}
vi who_wins(vi A , vi R , vi u , vi v){
    n = A.size(); m = u.size(); a = A; ch = R;
    vi ans; for(int i = 0 ; i < n ; i++) ans.pb(0);
    for(int i = 0 ; i < m ; i++){
        adj[u[i]].pb(v[i]); rev[v[i]].pb(u[i]);
    }
    for(int i = 0 ; i < n ; i++) if(!vis[i]) dfs(i);
    memset(vis , 0 , sizeof vis);
    while(!st.empty()){
        int x = st.top(); st.pop() ; dfs2(x);
        scc.pb(no);
        no.clear();
    }
    for(int i = 0 ; i < n ; i++) if(ch[i] && (scc[idx[i]].size() > 1 || adj[i][0] == i)) nice[i] = true;
    for(int i = 0 ; i < n ; i++) memset(vis , 0 , sizeof vis),ans[i] = dfs3(i);
    return ans;
}
/*int main(){
    //ifstream fin ("testing.txt");
    //ofstream fout ("output.txt");
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int nn , mm; cin>>nn>>mm;
    vi u(mm) , v(mm) , aa(nn) , cc(nn);
    for(int i = 0 ; i < nn ; i++) cin>>aa[i];
    for(int i = 0 ; i < nn ; i++) cin>>cc[i];
    for(int i = 0 ; i < mm ; i++) cin>>u[i]>>v[i];
    for(auto c : who_wins(aa , cc , u , v)  ) cout << c << " "; cout << "\n";
    return 0;
}*/
/*
6 11
0 1 1 1 0 1
0 1 0 0 1 1
0 0
1 1
2 2
3 3
4 4
5 5
0 1
1 2
2 3
3 4
4 5
*/
/*
    Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO / HLD
    Read the statement CAREFULLY !!
    Make a GREADY APPROACH !!!! (start from highest / lowest)
    Make your own TESTS !!
    Be careful from CORNER CASES !
*/

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	1620 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	468 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	135 ms	2044 KB	Output is correct
2	Correct	131 ms	2140 KB	Output is correct
3	Correct	148 ms	1956 KB	Output is correct
4	Correct	8 ms	1884 KB	Output is correct
5	Correct	106 ms	1876 KB	Output is correct
6	Correct	448 ms	1756 KB	Output is correct
7	Correct	8 ms	1748 KB	Output is correct
8	Correct	141 ms	1748 KB	Output is correct
9	Correct	230 ms	1748 KB	Output is correct
10	Correct	99 ms	1748 KB	Output is correct
11	Correct	144 ms	1672 KB	Output is correct
12	Incorrect	24 ms	1876 KB	3rd lines differ - on the 854th token, expected: '1', found: '0'
13	Halted	0 ms	0 KB	-