oj.uz

Submission #574618

# Submission time Handle Problem Language Result Execution time Memory
574618 2022-06-08T23:50:56 Z definitelynotmee Toy Train (IOI17_train) C++
27 / 100
 998 ms 262144 KB 
#include<bits/stdc++.h>
#include"train.h"
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	int owned = accumulate(all(a),0);
    int n = a.size(), m = u.size();
    vector<int> resp(n);
    matrix<int> g(n), rev(n);
    bool flag = 1;
    for(int i = 0; i < m; i++){
        g[u[i]].push_back(v[i]);
        rev[v[i]].push_back(u[i]);
        flag&=v[i] == u[i] || v[i] == u[i]+1;
    }
    if(owned == n){
        for(int i = 0; i < n; i++){
            if(!r[i])
                continue;
            vector<int> reach(n), reachedby(n);
            auto dfs =[&](int id, auto dfs)->void{
                reach[id] = 1;
                for(int i : g[id])
                    if(!reach[i]) dfs(i,dfs);
            };
            auto rdfs =[&](int id, auto dfs)->void{
                reachedby[id] = 1;
                for(int i : rev[id])
                    if(!reachedby[i]) dfs(i,dfs);
            };
            for(int j : g[i])
                dfs(j,dfs);
            for(int j : rev[i])
                rdfs(j,rdfs);
            if(reach[i]){
                for(int j = 0; j < n; j++)
                    resp[j]|=reachedby[j];
            }
        }       
        
    } else if(owned == 0){
        for(int i = 0; i < n; i++){
            if(r[i])
                continue;
            vector<int> reach(n), reachedby(n);
            auto dfs =[&](int id, auto dfs)->void{
                reach[id] = 1;
                for(int i : g[id])
                    if(!reach[i] && !r[i]) dfs(i,dfs);
            };
            auto rdfs =[&](int id, auto dfs)->void{
                reachedby[id] = 1;
                for(int i : rev[id])
                    if(!reachedby[i]) dfs(i,dfs);
            };
            for(int j : g[i])
                if(!r[j])dfs(j,dfs);
            for(int j : rev[i])
                rdfs(j,rdfs);
            if(reach[i]){
                for(int j = 0; j < n; j++)
                    resp[j]|=reachedby[j];
            }
        } 
        for(int& i : resp)
            i^=1;
    } else if(flag){
        for(int i = n-1; i >= 0; i--){
            int t1 = 0, t2 = 0;
            for(int j : g[i]){
                if(j == i)
                    t1 = 1;
                else if(j == i+1)
                    t2 = 1;
            }
            if(a[i]){
                if(t2){
                    resp[i] = resp[i+1];
                }
                if(t1 && r[i])
                    resp[i] = 1;
            } else {
                resp[i] = 1;
                if(t2){
                    resp[i] = resp[i+1];
                }
                if(t1 && !r[i])
                    resp[i] = 0;
            }
        }
    } else {
        vector<int> power(16,1);
        for(int i = 1; i < 16; i++)
            power[i] = power[i-1]*3;
        matrix<int> can(power[n],vector<int>(n));
        auto getbit =[&](int x, int id){
            return( x%(power[id]*3)-x%power[id])/power[id];
        };
        auto solve=[&](int id, int mask, auto solve)->int{
            int resp = a[id]^1;
            for(int i : g[id]){
                int newmask = mask;
                int state = getbit(mask,i);
                // << id << ' ' << mask << "=>" << i << ":\n";
                if(state == 1){
                    // << 'a' << '\n';
                    if(!a[id]){
                        resp = 0;
                        break;
                    }
                } else if(state == 2){
                    // << 'b' << '\n';
                    if(a[id]){
                        resp = 1;
                        break;
                    }
                } else {
                    if(r[i]){
                        for(int j = 0; j < n; j++){
                            if(getbit(newmask,j) == 1){
                                newmask+=power[j];
                            }
                        }
                        newmask+=power[i]*2;
                    } else {
                        newmask+=power[i];
                    }
                    // << newmask << '\n';
                    int cur = solve(i,newmask,solve);
                    if(cur == a[id]){
                        resp = cur;
                        break;
                    }
                }
            }
            // << id << ' ' << mask << " tem resp " << resp << '\n';
            return resp;
        };
        for(int i = 0; i < n; i++){
            int mask = power[i]*(1+r[i]);
            resp[i] = solve(i,mask,solve);
        }
    }
	return resp;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 980 KB Output is correct
2 Correct 5 ms 1028 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 5 ms 980 KB Output is correct
5 Correct 4 ms 976 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 10 ms 1076 KB Output is correct
8 Correct 10 ms 980 KB Output is correct
9 Correct 4 ms 980 KB Output is correct
10 Correct 4 ms 980 KB Output is correct
11 Correct 4 ms 980 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 176 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1768 KB Output is correct
2 Correct 90 ms 1748 KB Output is correct
3 Correct 143 ms 1748 KB Output is correct
4 Correct 537 ms 1660 KB Output is correct
5 Correct 99 ms 1740 KB Output is correct
6 Correct 86 ms 1616 KB Output is correct
7 Correct 507 ms 1580 KB Output is correct
8 Correct 8 ms 1492 KB Output is correct
9 Correct 7 ms 1460 KB Output is correct
10 Correct 10 ms 1568 KB Output is correct
11 Correct 7 ms 1436 KB Output is correct
12 Correct 7 ms 1492 KB Output is correct
13 Correct 8 ms 1620 KB Output is correct
14 Correct 8 ms 1596 KB Output is correct
15 Correct 8 ms 1620 KB Output is correct
16 Correct 8 ms 1620 KB Output is correct
17 Correct 8 ms 1620 KB Output is correct
18 Correct 303 ms 1324 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1364 KB Output is correct
2 Correct 296 ms 1456 KB Output is correct
3 Correct 474 ms 1576 KB Output is correct
4 Correct 290 ms 1492 KB Output is correct
5 Correct 691 ms 1592 KB Output is correct
6 Correct 588 ms 1596 KB Output is correct
7 Correct 580 ms 1560 KB Output is correct
8 Correct 380 ms 1528 KB Output is correct
9 Correct 9 ms 1516 KB Output is correct
10 Correct 227 ms 1680 KB Output is correct
11 Correct 93 ms 1588 KB Output is correct
12 Correct 239 ms 1740 KB Output is correct
13 Correct 998 ms 1636 KB Output is correct
14 Correct 590 ms 1520 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2772 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 980 KB Output is correct
2 Correct 5 ms 1028 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 5 ms 980 KB Output is correct
5 Correct 4 ms 976 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 10 ms 1076 KB Output is correct
8 Correct 10 ms 980 KB Output is correct
9 Correct 4 ms 980 KB Output is correct
10 Correct 4 ms 980 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Runtime error 176 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -