oj.uz

Submission #83806

# Submission time Handle Problem Language Result Execution time Memory
83806 2018-11-10T19:46:17 Z updown1 Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 622 ms 115016 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) {
    vis[at] = true;
    for (int i: inp[at]) if (!vis[i]) {
        adj[at].pb(i);
        go(i);
    }
}
void go2 (int at) {
    if (at == T) {toT[at] = T; return;}
    if (adj[at].empty()) return;
    vector<int> tim;
    for (int i: adj[at]) {
        go2(i);
        if (toT[i] != -1) {toT[at] = i; moves[at] += moves[i];}
        else tim.pb(moves[i]);
    }
    sort(tim.begin(), tim.end());
    For (i, 0, tim.size()) {
        if (i%2 == 0) moves[at]++;
        else moves[at] += 1 + tim[i];
    }
}

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);
    w<< moves[M]<<e;
}

Compilation message

mousetrap.cpp: In function 'void go2(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:41:10:
     For (i, 0, tim.size()) {
          ~~~~~~~~~~~~~~~~           
mousetrap.cpp:41:5: note: in expansion of macro 'For'
     For (i, 0, tim.size()) {
     ^~~
mousetrap.cpp: At global scope:
mousetrap.cpp:47:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 45 ms 47476 KB Output is correct
3 Correct 44 ms 47476 KB Output is correct
4 Correct 46 ms 47476 KB Output is correct
5 Incorrect 44 ms 47476 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 622 ms 115016 KB Output isn't correct
2 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 45 ms 47476 KB Output is correct
3 Correct 44 ms 47476 KB Output is correct
4 Correct 46 ms 47476 KB Output is correct
5 Incorrect 44 ms 47476 KB Output isn't correct
6 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 45 ms 47476 KB Output is correct
3 Correct 44 ms 47476 KB Output is correct
4 Correct 46 ms 47476 KB Output is correct
5 Incorrect 44 ms 47476 KB Output isn't correct
6 Halted 0 ms 0 KB -