Submission #1077962

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1077962	2024-08-27T11:13:00 Z	TB_	Toy Train (IOI17_train)	C++17	11 / 100	9 ms	2908 KB

train

#include <bits/stdc++.h>

using namespace std;
#define ll long long 
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define F first 
#define S second 
#define pb push_back 
#define deb(x) cout << #x << " = " << (x) << endl
#define deb2(x, y) cout << #x << " = " << (x)  << ", " << #y << " = " << (y) << endl

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;

ll n;
vl topo;
int seen[6000];
vvl adj(6000);
vvl adjr(6000);
vvl adjR(6000);

void toposort(int u){
    if(seen[u]) return;
    seen[u] = 1;
    for(auto &v : adjr[u]){
        toposort(v);
    }
    topo.pb(u);
}

int c = 0;

int dfs(int u){
    if(seen[u]) return 0;
    seen[u] = c;
    ll ans = 1;
    for(auto &v : adj[u]){
        ans+=dfs(v);
    }
    return ans;
}

vector<int> res;

void dfs2(int u){
    if(res[u]) return;
    res[u] = 1;
    for(auto &v : adjR[u]){
        dfs2(v);
    }
}


std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
    n = a.size();
    ll m = u.size();

    vl selfEdge(n+1, 0);
    fo(i, m){
        if(u[i] == v[i]) selfEdge[u[i]] = 1;
        else{
            adj[u[i]].pb(v[i]);
            adjr[v[i]].pb(u[i]);
            adjR[v[i]].pb(u[i]);
        }
    }

    memset(seen, 0, sizeof(seen));
	fo(i, n){
        if(seen[i]) continue;
        toposort(i);
    }
    reverse(all(topo));
    memset(seen, 0, sizeof(seen));
    vl good;
    fo(i, n){
        if(seen[topo[i]]) continue;
        c++;
        ll siz = dfs(topo[i]);
        // deb2(topo[i], siz);
        if(siz>1 || selfEdge[topo[i]]) good.pb(topo[i]);
    }
    vector<int> bla(n+1, 0);
    fo(i, r.size()){
        if(r[i]){
        // deb(seen[i]);
        bla[seen[i]] = 1;

        }
    }
    // fo(i, n+1) deb(bla[i]);
    res.assign(n, 0);
    fo(i, good.size()){
        // deb(good[i]);
        if(bla[seen[good[i]]]){
            // deb(seen[good[i]]);
            dfs2(good[i]);

        }
    }

	return res;
}

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:5:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define fo(i, n) for(ll i = 0; i<(n); i++)
      |                                 ^
train.cpp:89:5: note: in expansion of macro 'fo'
   89 |     fo(i, r.size()){
      |     ^~
train.cpp:5:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define fo(i, n) for(ll i = 0; i<(n); i++)
      |                                 ^
train.cpp:98:5: note: in expansion of macro 'fo'
   98 |     fo(i, good.size()){
      |     ^~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	1884 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	0 ms	860 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	7 ms	2908 KB	Output is correct
2	Correct	5 ms	2728 KB	Output is correct
3	Correct	6 ms	2640 KB	Output is correct
4	Correct	8 ms	2652 KB	Output is correct
5	Correct	7 ms	2652 KB	Output is correct
6	Correct	8 ms	2396 KB	Output is correct
7	Correct	7 ms	2396 KB	Output is correct
8	Correct	7 ms	2396 KB	Output is correct
9	Correct	7 ms	2392 KB	Output is correct
10	Correct	7 ms	2392 KB	Output is correct
11	Correct	7 ms	2396 KB	Output is correct
12	Correct	6 ms	2140 KB	Output is correct
13	Correct	7 ms	2652 KB	Output is correct
14	Correct	7 ms	2652 KB	Output is correct
15	Correct	7 ms	2720 KB	Output is correct
16	Correct	7 ms	2652 KB	Output is correct
17	Correct	9 ms	2584 KB	Output is correct
18	Correct	5 ms	1880 KB	Output is correct