oj.uz

Submission #1063385

# Submission time Handle Problem Language Result Execution time Memory
1063385 2024-08-17T17:44:23 Z Andrey Stray Cat (JOI20_stray) C++14
15 / 100
 33 ms 22112 KB 
#include "Anthony.h"
#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> haha[200001];
vector<int> dp(200001);
vector<int> troll(0);
int bruhseq[6] = {0,1,0,0,1,1};

void dfs(int a, int t, int d) {
    int br = 0,x = -1;
    for(pair<int,int> v: haha[a]) {
        if(v.first != t) {
            dfs(v.first,a,d+1);
            br++;
            x = dp[v.first];
        }
    }
    if(br == 1) {
        dp[a] = x+1;
        for(auto v: haha[a]) {
            if(v.first != t) {
                if(x == -1) {
                    troll[v.second] = d%2;
                }
                else {
                    troll[v.second] = bruhseq[x%6];
                }
            }
        }
    }
    else {
        dp[a] = -1;
        for(pair<int,int> v: haha[a]) {
            if(v.first != t) {
                troll[v.second] = d%2;
            }
        }
    }
}

std::vector<int> Mark(int n, int m, int a, int b, std::vector<int> u, std::vector<int> v) {
    for(int i = 0; i < m; i++) {
        haha[u[i]].push_back({v[i],i});
        haha[v[i]].push_back({u[i],i});
    }
    if(a > 2) {
        vector<int> br(n,INT_MAX);
        br[0] = 0;
        queue<int> idk;
        idk.push(0);
        vector<int> ans(m,-1);
        while(!idk.empty()) {
            int u = idk.front();
            idk.pop();
            for(pair<int,int> v: haha[u]) {
                if(br[v.first] == INT_MAX) {
                    br[v.first] = br[u]+1;
                    idk.push(v.first);
                }
            }
        }
        for(int i = 0; i < m; i++) {
            if(ans[i] == -1) {
                int c = min(br[u[i]],br[v[i]])%3;
                ans[i] = c;
            }
        }
        return ans;
    }
    else {
        troll.resize(n-1);
        dfs(0,-1,1);
        return troll;
    }
}

#include "Catherine.h"
#include<bits/stdc++.h>
using namespace std;

int A;
int seq[6] = {0,1,0,0,1,1};
vector<int> wow(0);
bool first = true;
bool yeah = true;

void Init(int a, int b) {
    A = a;
}

int Move(vector<int> haha) {
    if(A > 2) {
        vector<int> wow(0);
        for(int i = 0; i < haha.size(); i++) {
            if(haha[i] >= 1) {
                wow.push_back(i);
            }
        }
        if(wow.size() == 1) {
            return wow[0];
        }
        else if(wow.size() == 2) {
            if(wow[0] == 0 && wow[1] == 1) {
                return 0;
            }
            else if(wow[0] == 1 && wow[1] == 2) {
                return 1;
            }
            else {
                return 2;
            }
        }
    }
    else {
        if(first) {
            first = false;
            if(haha[0] > 1 || haha[1] == 0) {
                yeah = false;
                wow.push_back(1);
                return 1;
            }
            else if(haha[1] > 1 || haha[0] == 0) {
                yeah = false;
                wow.push_back(0);
                return 0;
            }
            else {
                wow.push_back(0);
                return 0;
            }
        }
        else {
            if(yeah) {
                if(haha[0]+haha[1] > 1) {
                    yeah = false;
                    if(haha[0] == 0 || haha[1] == 0) {
                        return -1;
                    }
                    else {
                        if(wow[wow.size()-1] == 1) {
                            wow.push_back(1);
                            return 0;
                        }
                        else {
                            wow.push_back(0);
                            return 1;
                        }
                    }
                }
                else if(wow.size() == 6) {
                    for(int i = 0; i < 6; i++) {
                        bool bubu = true;
                        for(int j = i; j < i+6; j++) {
                            if(seq[j-i] != wow[j%6]) {
                                bubu = false;
                            }
                        }
                        if(bubu) {
                            yeah = false;
                            break;
                        }
                    }
                    if(yeah) {
                        yeah = false;
                        return -1;
                    }
                    else {
                        if(haha[0] > 0) {
                            wow.push_back(0);
                            return 0;
                        }
                        else {
                            wow.push_back(1);
                            return 1;
                        }
                    }
                }
                else {
                    if(haha[0]+haha[1] == 0) {
                        yeah = false;
                        return -1;
                    }
                    else {
                        if(haha[0] > 0) {
                            wow.push_back(0);
                            return 0;
                        }
                        else {
                            wow.push_back(1);
                            return 1;
                        }
                    }
                }
            }
            else {
                if(haha[0] == 0 || wow[wow.size()-1] == 0) {
                    return 1;
                }
                else {
                    return 0;
                }
            }
        }
    }
}

Compilation message

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:18:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int i = 0; i < haha.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
Catherine.cpp:129:1: warning: control reaches end of non-void function [-Wreturn-type]
  129 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 21092 KB Output is correct
2 Correct 2 ms 6200 KB Output is correct
3 Correct 22 ms 20536 KB Output is correct
4 Correct 31 ms 22112 KB Output is correct
5 Correct 32 ms 22056 KB Output is correct
6 Correct 26 ms 20828 KB Output is correct
7 Correct 27 ms 20892 KB Output is correct
8 Correct 31 ms 21480 KB Output is correct
9 Correct 33 ms 21756 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 21092 KB Output is correct
2 Correct 2 ms 6200 KB Output is correct
3 Correct 22 ms 20536 KB Output is correct
4 Correct 31 ms 22112 KB Output is correct
5 Correct 32 ms 22056 KB Output is correct
6 Correct 26 ms 20828 KB Output is correct
7 Correct 27 ms 20892 KB Output is correct
8 Correct 31 ms 21480 KB Output is correct
9 Correct 33 ms 21756 KB Output is correct
10 Correct 24 ms 18844 KB Output is correct
11 Correct 24 ms 19032 KB Output is correct
12 Correct 24 ms 19048 KB Output is correct
13 Correct 26 ms 18856 KB Output is correct
14 Correct 26 ms 19200 KB Output is correct
15 Correct 27 ms 19540 KB Output is correct
16 Correct 28 ms 21644 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 18536 KB Output is correct
2 Correct 2 ms 6192 KB Output is correct
3 Correct 22 ms 18244 KB Output is correct
4 Correct 31 ms 20072 KB Output is correct
5 Correct 30 ms 19980 KB Output is correct
6 Correct 26 ms 18516 KB Output is correct
7 Correct 26 ms 18536 KB Output is correct
8 Correct 31 ms 19300 KB Output is correct
9 Correct 28 ms 19292 KB Output is correct
10 Correct 27 ms 19036 KB Output is correct
11 Correct 27 ms 19048 KB Output is correct
12 Correct 28 ms 19496 KB Output is correct
13 Correct 28 ms 18984 KB Output is correct
14 Correct 28 ms 19408 KB Output is correct
15 Correct 31 ms 19304 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 18536 KB Output is correct
2 Correct 2 ms 6192 KB Output is correct
3 Correct 22 ms 18244 KB Output is correct
4 Correct 31 ms 20072 KB Output is correct
5 Correct 30 ms 19980 KB Output is correct
6 Correct 26 ms 18516 KB Output is correct
7 Correct 26 ms 18536 KB Output is correct
8 Correct 31 ms 19300 KB Output is correct
9 Correct 28 ms 19292 KB Output is correct
10 Correct 27 ms 19036 KB Output is correct
11 Correct 27 ms 19048 KB Output is correct
12 Correct 28 ms 19496 KB Output is correct
13 Correct 28 ms 18984 KB Output is correct
14 Correct 28 ms 19408 KB Output is correct
15 Correct 31 ms 19304 KB Output is correct
16 Correct 23 ms 17044 KB Output is correct
17 Correct 24 ms 16984 KB Output is correct
18 Correct 25 ms 17204 KB Output is correct
19 Correct 23 ms 16992 KB Output is correct
20 Correct 26 ms 17744 KB Output is correct
21 Correct 26 ms 17748 KB Output is correct
22 Correct 28 ms 19360 KB Output is correct
23 Correct 24 ms 17256 KB Output is correct
24 Correct 23 ms 17244 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6452 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 16636 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 16728 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -