Submission #83809

#	Time	Username	Problem	Language	Result	Execution time	Memory
83809		updown1	Mousetrap (CEOI17_mousetrap)	C++17	20 / 100	1399 ms	120556 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) {
    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 (stderr)

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