oj.uz

Submission #309628

# Submission time Handle Problem Language Result Execution time Memory
309628 2020-10-04T02:17:55 Z jainbot27 Stray Cat (JOI20_stray) C++17
15 / 100
 68 ms 17420 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}

const char nl = '\n';
const int mxN = 20010;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

int n, m, a, b, d[mxN]; 
vi U, V, adj[mxN], res;
queue<int> q;

int amt[3] = {0, 1, 2};
vi Mark(int N, int M, int A, int B, vi Uu, vi Vv){
    U = Uu; V = Vv; n = N; m = M; a = A; b = B;
    if(a==2){
        assert(false);
    }
    else{
        res.resize(m);
        F0R(i, n) d[i] = MOD;
        F0R(i, m){
            adj[U[i]].pb(V[i]);
            adj[V[i]].pb(U[i]);
        }
        d[0] = 0;
        q.push(0);
        while(!q.empty()){
            int u = q.front(); q.pop();
            trav(v, adj[u]){
                if(ckmin(d[v], d[u]+1)){
                    q.push(v);
                }
            }
        }
        F0R(i, m){
            // we want to give them the value of the vertex with the higher value so that we know where to go
            if(d[U[i]]<d[V[i]])
                swap(U[i], V[i]);
            if(d[U[i]]==d[V[i]]){
                res[i] = amt[d[U[i]]%3];
            }
            else{
                res[i] = amt[d[V[i]]%3];
                // if we have distance 2 and 3
                // we will at 3 see that we have 2
            }
        }
        return res;
    }
}

#ifdef ACMX
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N, M, A, B; cin >> N >> M >> A >> B;
    U.resize(M);
    V.resize(M);
    F0R(i, M){
        cin >> U[i] >> V[i];     
    }
    vi res = Mark(N, M, A, B, U, V);
    trav(x, res){
        cout << x << " ";
    }
    cout << nl;

    return 0;
}
#endif
#include <vector>
#include <iostream>
#include <queue>
#include <cassert>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}

const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

int a, b;
void Init(int A, int B){
    a = A, b = B;
    assert(b==0&&a>=3);
}
int Move(vi y){
    if(y[0] == 0 && y[1] == 0 && y[2] == 0){
        assert(false);
    }
    else if(y[0] == 0 && y[1] == 0){
        return 2;
    }
    else if(y[1] == 0 && y[2] == 0){
        return 0;
    }
    else if(y[2] == 0 && y[0] == 0){
        return 1;
    }
    else if(y[0] == 0){
        return 1;
    }
    else if(y[1] == 0){
        return 2;
    }
    else if(y[2] == 0){
        return 0;
    }
    else{
        assert(false);
    }
}
#ifdef ACMX
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);


    return 0;
}
#endif

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 15988 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 41 ms 15412 KB Output is correct
4 Correct 67 ms 17420 KB Output is correct
5 Correct 68 ms 17292 KB Output is correct
6 Correct 62 ms 15944 KB Output is correct
7 Correct 53 ms 16080 KB Output is correct
8 Correct 67 ms 16760 KB Output is correct
9 Correct 60 ms 16768 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 15988 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 41 ms 15412 KB Output is correct
4 Correct 67 ms 17420 KB Output is correct
5 Correct 68 ms 17292 KB Output is correct
6 Correct 62 ms 15944 KB Output is correct
7 Correct 53 ms 16080 KB Output is correct
8 Correct 67 ms 16760 KB Output is correct
9 Correct 60 ms 16768 KB Output is correct
10 Correct 46 ms 14024 KB Output is correct
11 Correct 49 ms 14024 KB Output is correct
12 Correct 46 ms 14144 KB Output is correct
13 Correct 45 ms 14276 KB Output is correct
14 Correct 49 ms 14412 KB Output is correct
15 Correct 54 ms 14628 KB Output is correct
16 Correct 59 ms 16844 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 13432 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 40 ms 13448 KB Output is correct
4 Correct 66 ms 15364 KB Output is correct
5 Correct 63 ms 15188 KB Output is correct
6 Correct 48 ms 13800 KB Output is correct
7 Correct 48 ms 13792 KB Output is correct
8 Correct 56 ms 14584 KB Output is correct
9 Correct 56 ms 14420 KB Output is correct
10 Correct 51 ms 14156 KB Output is correct
11 Correct 51 ms 14328 KB Output is correct
12 Correct 55 ms 14332 KB Output is correct
13 Correct 54 ms 14312 KB Output is correct
14 Correct 59 ms 14548 KB Output is correct
15 Correct 57 ms 14588 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 13432 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 40 ms 13448 KB Output is correct
4 Correct 66 ms 15364 KB Output is correct
5 Correct 63 ms 15188 KB Output is correct
6 Correct 48 ms 13800 KB Output is correct
7 Correct 48 ms 13792 KB Output is correct
8 Correct 56 ms 14584 KB Output is correct
9 Correct 56 ms 14420 KB Output is correct
10 Correct 51 ms 14156 KB Output is correct
11 Correct 51 ms 14328 KB Output is correct
12 Correct 55 ms 14332 KB Output is correct
13 Correct 54 ms 14312 KB Output is correct
14 Correct 59 ms 14548 KB Output is correct
15 Correct 57 ms 14588 KB Output is correct
16 Correct 43 ms 12108 KB Output is correct
17 Correct 43 ms 12292 KB Output is correct
18 Correct 46 ms 12168 KB Output is correct
19 Correct 43 ms 12476 KB Output is correct
20 Correct 53 ms 12772 KB Output is correct
21 Correct 49 ms 12592 KB Output is correct
22 Correct 56 ms 14724 KB Output is correct
23 Correct 47 ms 12352 KB Output is correct
24 Correct 46 ms 12564 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 2432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -