Submission #609590

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
609590	2022-07-27T17:44:30 Z	HediChehaidar	Toy Train (IOI17_train)	C++17	11 / 100	865 ms	2172 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)) nice[i] = true;
    for(int i = 0 ; i < n ; i++){
        if(ch[i]){
            for(auto c : adj[i]) if(c == 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	5 ms	1748 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
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	2172 KB	Output is correct
2	Correct	136 ms	2136 KB	Output is correct
3	Correct	136 ms	2084 KB	Output is correct
4	Correct	11 ms	2004 KB	Output is correct
5	Correct	106 ms	2004 KB	Output is correct
6	Correct	463 ms	1884 KB	Output is correct
7	Correct	9 ms	1840 KB	Output is correct
8	Correct	118 ms	1908 KB	Output is correct
9	Correct	233 ms	1884 KB	Output is correct
10	Correct	93 ms	1876 KB	Output is correct
11	Correct	138 ms	1804 KB	Output is correct
12	Correct	25 ms	1876 KB	Output is correct
13	Correct	581 ms	2132 KB	Output is correct
14	Correct	865 ms	2148 KB	Output is correct
15	Correct	689 ms	2100 KB	Output is correct
16	Correct	25 ms	2156 KB	Output is correct
17	Correct	124 ms	2096 KB	Output is correct
18	Correct	266 ms	1808 KB	Output is correct