oj.uz

Submission #36571

# Submission time Handle Problem Language Result Execution time Memory
36571 2017-12-10T16:10:58 Z WhipppedCream Multidrink (POI13_mul) C++14
80 / 100
 1000 ms 90396 KB 
#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 fuck(int u, int p)
{
    par[u] = p;
    for(auto v : adj[u])
    {
        if(v == p) continue;
        fuck(v, u);
    }
}
void dfs2(int u, int p)
{
    //printf("%d\n", u);
    cnt[u] = 1;
    for(auto v : adj[u])
    {
        if(v == par[u]) 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)
    {
        //printf("%d ", x);
        route.pb(x);
    }
    //printf("\n");
    if(nontriv.empty())
    {
        route.pb(u);
        return;
    }
    int v = nontriv[0];
    route.pb(v);
    printC(v);
    route.pb(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);
    }
    if(!nontriv.empty())
    {
        int v = nontriv[0];
        printA(v);
    }
    for(auto x : triv) route.pb(x);
}
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);
    fuck(1, 0);
    //dfs(n, par[n], -1);
    //printf("fuck off\n");
    dfs2(1, 0);
    //printf("hey\n");
    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]);
        }
    }
    //printf("-\n");
    for(auto x : route) printf("%d\n", x);
}

Compilation message

mul.cpp: In function 'int main()':
mul.cpp:206:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
mul.cpp:211: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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29364 KB Output is correct
2 Correct 9 ms 29364 KB Output is correct
3 Correct 3 ms 29364 KB Output is correct
4 Correct 3 ms 29364 KB Output is correct
5 Correct 3 ms 29364 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29364 KB Output is correct
2 Correct 6 ms 29364 KB Output is correct
3 Correct 6 ms 29364 KB Output is correct
4 Correct 0 ms 29364 KB Output is correct
5 Correct 3 ms 29364 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29364 KB Output is correct
2 Correct 6 ms 29364 KB Output is correct
3 Correct 9 ms 29364 KB Output is correct
4 Correct 6 ms 29364 KB Output is correct
5 Correct 9 ms 29364 KB Output is correct
6 Correct 0 ms 29364 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29364 KB Output is correct
2 Correct 6 ms 29364 KB Output is correct
3 Correct 6 ms 29364 KB Output is correct
4 Correct 0 ms 29364 KB Output is correct
5 Correct 9 ms 29364 KB Output is correct
6 Correct 6 ms 29364 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29364 KB Output is correct
2 Correct 3 ms 29364 KB Output is correct
3 Correct 3 ms 29364 KB Output is correct
4 Correct 3 ms 29364 KB Output is correct
5 Correct 3 ms 29364 KB Output is correct
6 Correct 6 ms 29364 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29364 KB Output is correct
2 Correct 0 ms 29364 KB Output is correct
3 Correct 9 ms 29364 KB Output is correct
4 Correct 3 ms 29364 KB Output is correct
5 Correct 6 ms 29364 KB Output is correct
6 Correct 3 ms 29364 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29364 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29364 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29364 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29364 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 29364 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 29364 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29364 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29632 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29496 KB Output is correct
2 Correct 3 ms 29364 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 34672 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 34984 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 32664 KB Output is correct
2 Correct 3 ms 29364 KB Output is correct

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 49188 KB Execution timed out

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 50216 KB Execution timed out

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 52508 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #22
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 90396 KB Execution timed out
2 Halted 0 ms 0 KB -