Submission #83806

#	Time	Username	Problem	Language	Result	Execution time	Memory
83806		updown1	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	622 ms	115016 KiB

mousetrap

#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 (stderr)

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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35