oj.uz

Submission #83808

# Submission time Handle Problem Language Result Execution time Memory
83808 2018-11-10T20:13:08 Z updown1 Mousetrap (CEOI17_mousetrap) C++17
20 / 100
 1477 ms 145796 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int ll
//500,000,000 operations
const int MAXN = 1000000;
//Global Variables
int N, T, M, moves[MAXN], toT[MAXN];
bool vis[MAXN];
vector<int> adj[MAXN], inp[MAXN];

void go(int at) {
    if (at == T) toT[at] = T;
    vis[at] = true;
    for (int i: inp[at]) if (!vis[i]) {
        adj[at].pb(i);
        go(i);
        if (toT[i] != -1) toT[at] = i;
    }
}
void go2 (int at, int curr) {
    //w<< at+1 s curr<<e;
    if (at == T || adj[at].empty()) return;
    vector<int> tim;
    for (int i: adj[at]) if (toT[at] != i) {
        go2(i, 0);
        tim.pb(moves[i]);
    }
    sort(tim.begin(), tim.end());
    reverse(tim.begin(), tim.end());
    if (toT[at] == -1) {
        For (i, 0, tim.size()) {
            if (i%2 == 0) moves[at]++;
            else moves[at] += 1 + tim[i];
        }
        return;
    }
    //w<< "HERE" s at+1<<e;
    reverse(tim.begin(), tim.end());
    while (curr > 0 && tim.size()) {curr--; moves[at]++; tim.pop_back();}
    reverse(tim.begin(), tim.end());
    //w<< at+1 <<';'; for (int j: tim) w s j; w<<e;
    For (i, 0, tim.size()) {
        if (i%2 == 0) moves[at]++;
        else moves[at] += 1 + tim[i];
    }
    int add = adj[at].size()%2;
    go2(toT[at], curr+add);
    moves[at] += moves[toT[at]];
}

main() {
	//ifstream cin("test.in");
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> T >> M; T--; M--;
    For (i, 1, N) {
        int a, b; cin >> a >> b; a--; b--; inp[a].pb(b); inp[b].pb(a);
    }
    ffi toT[i] = -1;
    go(M);
    //ffi {w<< i+1 << ":"; for (int j: adj[i]) w s j+1; w<<e;}
    go2(M, 0);
    //ffi w<< i+1 c moves[i]<<e;
    w<< moves[M]<<e;
}

Compilation message

mousetrap.cpp: In function 'void go2(ll, ll)':
mousetrap.cpp:4:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define For(i, a, b) for(int i=a; i<b; i++)
mousetrap.cpp:44:14:
         For (i, 0, tim.size()) {
              ~~~~~~~~~~~~~~~~       
mousetrap.cpp:44:9: note: in expansion of macro 'For'
         For (i, 0, tim.size()) {
         ^~~
mousetrap.cpp:4:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define For(i, a, b) for(int i=a; i<b; i++)
mousetrap.cpp:55:10:
     For (i, 0, tim.size()) {
          ~~~~~~~~~~~~~~~~           
mousetrap.cpp:55:5: note: in expansion of macro 'For'
     For (i, 0, tim.size()) {
     ^~~
mousetrap.cpp: At global scope:
mousetrap.cpp:64:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 45 ms 47428 KB Output is correct
3 Correct 45 ms 47520 KB Output is correct
4 Correct 44 ms 47540 KB Output is correct
5 Correct 43 ms 47540 KB Output is correct
6 Correct 44 ms 47540 KB Output is correct
7 Correct 45 ms 47556 KB Output is correct
8 Correct 44 ms 47556 KB Output is correct
9 Correct 45 ms 47660 KB Output is correct
10 Correct 44 ms 47660 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 115032 KB Output is correct
2 Correct 593 ms 120564 KB Output is correct
3 Incorrect 1477 ms 145796 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 45 ms 47428 KB Output is correct
3 Correct 45 ms 47520 KB Output is correct
4 Correct 44 ms 47540 KB Output is correct
5 Correct 43 ms 47540 KB Output is correct
6 Correct 44 ms 47540 KB Output is correct
7 Correct 45 ms 47556 KB Output is correct
8 Correct 44 ms 47556 KB Output is correct
9 Correct 45 ms 47660 KB Output is correct
10 Correct 44 ms 47660 KB Output is correct
11 Incorrect 45 ms 145796 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 45 ms 47428 KB Output is correct
3 Correct 45 ms 47520 KB Output is correct
4 Correct 44 ms 47540 KB Output is correct
5 Correct 43 ms 47540 KB Output is correct
6 Correct 44 ms 47540 KB Output is correct
7 Correct 45 ms 47556 KB Output is correct
8 Correct 44 ms 47556 KB Output is correct
9 Correct 45 ms 47660 KB Output is correct
10 Correct 44 ms 47660 KB Output is correct
11 Correct 668 ms 115032 KB Output is correct
12 Correct 593 ms 120564 KB Output is correct
13 Incorrect 1477 ms 145796 KB Output isn't correct
14 Halted 0 ms 0 KB -