oj.uz

Submission #1074730

# Submission time Handle Problem Language Result Execution time Memory
1074730 2024-08-25T13:21:42 Z zehnsechs Toy Train (IOI17_train) C++14
16 / 100
 2000 ms 7340 KB 
#include "train.h"
#include<bits/stdc++.h>

using namespace std;


void dfs(int v, vector<int>& x, vector<int>& c, vector<vector<int>>& adj, vector<int>& res){
    if (x[v]) res[v]=1;
    cerr << "vertex " << v << '\n';    
    if(res[v]){
        for(int u: adj[v]){
            cerr << "n " << u << '\n';
            if (u==v) continue;
            c[u]--;
            if(c[u]==0 && !res[u]) {
                res[u]=1;
                dfs(u,x,c,adj,res);
            }
        }
    }
}


vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	int n = a.size();
        int m = u.size();
        vector<int> res(n,1);
        vector<vector<int>> adj(n);
        vector<int> deg(n,0);
        
        //add the edges to adj in the opposite direction
        for(int i=0;i<m;++i){
            adj[v[i]].push_back(u[i]);
            deg[u[i]]++;
        }
        for(int i=0;i<n;++i){
            cerr << deg[i] << '\n';
        }
        
        bool con = true;
        while(con){
            con = false;
            vector<int> fa(n,0);
            vector<int> rm(n,0);
            vector<int> c0(n,1);
            vector<int> c1(n,1);
            for(int i=0;i<n;++i) (a[i] ? c1[i] = deg[i] : c0[i]= deg[i]);
            cerr << "fa" << '\n';
            for(int i=0;i<n;++i) if(r[i]&&res[i]) dfs(i,r,c0,adj,fa);
            vector<int> x(n,0);
            for(int i=0;i<n;++i) if(!fa[i]) x[i]=1;
            cerr << "fb" << '\n';
            for(int i=0;i<n;++i) if(!fa[i]&&res[i]) dfs(i,x,c1,adj,rm);
            for(int i=0;i<n;++i) if(rm[i]) {
                cerr << "unreachable " << i <<'\n';
                for(int u: adj[i]) deg[u]--;
                adj[i].clear();
                res[i]=0;
                con = true;
                }
        }



	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 1288 KB Output is correct
2 Correct 222 ms 1628 KB Output is correct
3 Correct 173 ms 1616 KB Output is correct
4 Correct 183 ms 1368 KB Output is correct
5 Correct 148 ms 1360 KB Output is correct
6 Correct 137 ms 1360 KB Output is correct
7 Correct 80 ms 1104 KB Output is correct
8 Correct 194 ms 1620 KB Output is correct
9 Correct 120 ms 1632 KB Output is correct
10 Correct 87 ms 1152 KB Output is correct
11 Correct 62 ms 1108 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 7340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 1608 KB Output is correct
2 Correct 149 ms 1636 KB Output is correct
3 Correct 172 ms 1872 KB Output is correct
4 Correct 183 ms 2392 KB Output is correct
5 Correct 180 ms 1876 KB Output is correct
6 Correct 172 ms 1872 KB Output is correct
7 Correct 166 ms 1876 KB Output is correct
8 Correct 163 ms 1872 KB Output is correct
9 Correct 153 ms 1620 KB Output is correct
10 Correct 102 ms 1572 KB Output is correct
11 Correct 113 ms 1748 KB Output is correct
12 Correct 101 ms 1524 KB Output is correct
13 Correct 170 ms 1872 KB Output is correct
14 Correct 156 ms 1876 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 1288 KB Output is correct
2 Correct 222 ms 1628 KB Output is correct
3 Correct 173 ms 1616 KB Output is correct
4 Correct 183 ms 1368 KB Output is correct
5 Correct 148 ms 1360 KB Output is correct
6 Correct 137 ms 1360 KB Output is correct
7 Correct 80 ms 1104 KB Output is correct
8 Correct 194 ms 1620 KB Output is correct
9 Correct 120 ms 1632 KB Output is correct
10 Correct 87 ms 1152 KB Output is correct
11 Correct 62 ms 1108 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Incorrect 1 ms 348 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
16 Halted 0 ms 0 KB -