oj.uz

Submission #83809

# Submission time Handle Problem Language Result Execution time Memory
83809 2018-11-10T20:22:42 Z updown1 Mousetrap (CEOI17_mousetrap) C++17
20 / 100
 1399 ms 120556 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 = 1-tim.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 44 ms 47352 KB Output is correct
2 Correct 43 ms 47352 KB Output is correct
3 Correct 48 ms 47552 KB Output is correct
4 Correct 42 ms 47552 KB Output is correct
5 Correct 43 ms 47552 KB Output is correct
6 Correct 43 ms 47552 KB Output is correct
7 Correct 43 ms 47552 KB Output is correct
8 Correct 64 ms 47552 KB Output is correct
9 Correct 44 ms 47552 KB Output is correct
10 Correct 43 ms 47552 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 115068 KB Output is correct
2 Correct 596 ms 115068 KB Output is correct
3 Incorrect 1399 ms 120556 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 43 ms 47352 KB Output is correct
3 Correct 48 ms 47552 KB Output is correct
4 Correct 42 ms 47552 KB Output is correct
5 Correct 43 ms 47552 KB Output is correct
6 Correct 43 ms 47552 KB Output is correct
7 Correct 43 ms 47552 KB Output is correct
8 Correct 64 ms 47552 KB Output is correct
9 Correct 44 ms 47552 KB Output is correct
10 Correct 43 ms 47552 KB Output is correct
11 Incorrect 43 ms 120556 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 43 ms 47352 KB Output is correct
3 Correct 48 ms 47552 KB Output is correct
4 Correct 42 ms 47552 KB Output is correct
5 Correct 43 ms 47552 KB Output is correct
6 Correct 43 ms 47552 KB Output is correct
7 Correct 43 ms 47552 KB Output is correct
8 Correct 64 ms 47552 KB Output is correct
9 Correct 44 ms 47552 KB Output is correct
10 Correct 43 ms 47552 KB Output is correct
11 Correct 650 ms 115068 KB Output is correct
12 Correct 596 ms 115068 KB Output is correct
13 Incorrect 1399 ms 120556 KB Output isn't correct
14 Halted 0 ms 0 KB -