Submission #36566

#	Time	Username	Problem	Language	Result	Execution time	Memory
36566		WhipppedCream	Multidrink (POI13_mul)	C++14	4 / 100	1000 ms	262144 KiB

mul

#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vvi vector< vi >
#define vii vector< ii >
#define mp make_pair
#define pb push_back
const int maxn = 5e5+5;
vector<int> adj[maxn];
int n;
int way[maxn], par[maxn], cnt[maxn];
int deg[maxn];
int aa[maxn], bb[maxn], cc[maxn];
int arr[maxn];
int k;
vector<int> tour;
vector<int> route;
int dfs(int u, int p, int dest)
{
    //printf("%d\n", u);
    par[u] = p;
    if(u == dest) return 1;
    for(auto v : adj[u])
    {
        if(v == p) continue;
        int x = dfs(v, u, dest);
        if(x)
        {
            way[u] = 1;
        }
    }
    if(way[u]) tour.pb(u);
    return way[u];
}
void dfs2(int u, int p)
{
    cnt[u] = 1;
    for(auto v : adj[u])
    {
        if(v == p) continue;
        dfs2(v, u);
        if(!way[v]) cnt[u] += cnt[v];
    }
}
int A(int);
int B(int);
int C(int);
void printA(int);
void printB(int);
void printC(int);
int A(int u)
{
    if(aa[u] != -1) return aa[u];
    int cnt = 0;
    for(auto v : adj[u])
    {
        if(v == par[u]) continue;
        if(deg[v] == 1) continue;
        if(way[v]) continue;
        if(!C(v)) return aa[u] = 0;
        else cnt++;
        if(cnt == 2) return aa[u] = 0;
    }
    return aa[u] = 1;
}
int B(int u)
{
    if(bb[u] != -1) return bb[u];
    vector<int> nontriv;
    for(auto v : adj[u])
    {
        if(v != par[u] && deg[v]> 1 && !way[v]) nontriv.pb(v);
    }
    if(nontriv.size()>= 3) return bb[u] = 0;
    if(nontriv.size() == 0) return bb[u] = 1;
    if(nontriv.size() == 1)
    {
        int v = nontriv[0];
        return bb[u] = A(v);
    }
    int v1 = nontriv[0], v2 = nontriv[1];
    return bb[u] = (A(v1) and C(v2)) or (A(v2) and C(v1));
}
int C(int u)
{
    if(cc[u] != -1) return cc[u];
    vector<int> nontriv;
    for(auto v : adj[u])
    {
        if(v != par[u] && deg[v]> 1 && !way[v]) nontriv.pb(v);
    }
    if(nontriv.size()>= 2) return cc[u] = 0;
    if(nontriv.size() == 0) return cc[u] = 1;
    int v = nontriv[0];
    return cc[u] = A(v);
}
int ma()
{
    reverse(tour.begin(), tour.end());
    k = tour.size();
    for(int i = 0; i< k; i++)
    {
        int u = tour[i];
        if(cnt[u] == 1) arr[i+1] = 0;
        else if(i && A(u) && arr[i]<= 1) arr[i+1] = 1;
        else if(i && B(u) && arr[i]< 2) arr[i+1] = 2;
        else if(C(u)) arr[i+1] = 3;
        else return 0;
    }
    return arr[k] <= 1;
}
void printA(int u)
{
    //printf("called %d\n", u);
    vector<int> triv;
    vector<int> nontriv;
    for(auto v : adj[u])
    {
        if(way[v] or v == par[u]) continue;
        if(deg[v] == 1) triv.pb(v);
        else nontriv.pb(v);
    }
    for(auto x : triv) route.pb(x);
    if(nontriv.empty())
    {
        route.pb(u);
        return;
    }
    int v = nontriv[0];
    route.pb(v);
    printC(u);
}
void printB(int u)
{
    vector<int> triv;
    vector<int> nontriv;
    for(auto v : adj[u])
    {
        if(way[v] or v == par[u]) continue;
        if(deg[v] == 1) triv.pb(v);
        else nontriv.pb(v);
    }
    for(auto x : triv) route.pb(x);
    if(nontriv.empty()) return;
    if(nontriv.size() == 1)
    {
        route.pb(u);
        printA(nontriv[0]);
    }
    else
    {
        int v1 = nontriv[0], v2 = nontriv[1];
        if(!C(v1)) swap(v1, v2);
        route.pb(v1);
        printC(v1);
        route.pb(u);
        printA(v2);
    }
}
void printC(int u)
{
    vector<int> triv;
    vector<int> nontriv;
    for(auto v : adj[u])
    {
        if(way[v] or v == par[u]) continue;
        if(deg[v] == 1) triv.pb(v);
        else nontriv.pb(v);
    }
    for(auto x : triv) route.pb(x);
    if(nontriv.empty()) return;
    int v = nontriv[0];
    printA(v);
}
int main()
{
    //#ifndef atom
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    //#endif
    memset(aa, -1, sizeof aa); memset(bb, -1, sizeof bb);
    memset(cc, -1, sizeof cc);
    scanf("%d", &n);
    tour.pb(n);
    way[n] = 1;
    for(int i = 1; i< n; i++)
    {
        int a, b; scanf("%d %d", &a, &b);
        adj[a].pb(b); adj[b].pb(a);
    }
    for(int i = 2; i<= n; i++) deg[i] = adj[i].size();
    dfs(1, 0, n);
    dfs2(1, 0);
    if(!ma())
    {
        printf("BRAK\n");
        return 0;
    }
    //for(int i = 1; i<= n; i++) printf("p[%d] = %d\n", i, par[i]);
    //for(int i = 0; i< k; i++) printf("is(per%d)%d(%d, %d, %d)(%d)\n", cnt[tour[i]], tour[i], A(tour[i]), B(tour[i]), C(tour[i]), arr[i+1]);
    for(int i = 1; i<= k; i++)
    {
        if(arr[i] == 0) route.pb(tour[i-1]);
        else if(arr[i] == 1) printA(tour[i-1]);
        else if(arr[i] == 2) printB(tour[i-1]);
        else
        {
            route.pb(tour[i-1]);
            printC(tour[i-1]);
        }
    }
    for(auto x : route) printf("%d\n", x);
}

Compilation message (stderr)

mul.cpp: In function 'int main()':
mul.cpp:188:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
mul.cpp:193:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d %d", &a, &b);
                                         ^

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 4 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 0 / 4
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5