oj.uz

Submission #36566

# Submission time Handle Problem Language Result Execution time Memory
36566 2017-12-10T15:41:37 Z WhipppedCream Multidrink (POI13_mul) C++14
4 / 100
 1000 ms 262144 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 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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 29364 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 0 ms 29364 KB Expected EOF
4 Halted 0 ms 0 KB -

Subtask #3
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 Incorrect 3 ms 29364 KB Expected EOF
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 9 ms 29364 KB Output is correct

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 56 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 29364 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 29364 KB Not a permutation.

Subtask #8
0 / 4.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 89 ms 262144 KB Memory limit exceeded

Subtask #9
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 29364 KB Expected EOF

Subtask #10
0 / 4.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 106 ms 262144 KB Memory limit exceeded

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 29364 KB Expected EOF

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 29364 KB Expected EOF

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 109 ms 262144 KB Memory limit exceeded

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 29640 KB Expected EOF

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 189 ms 262144 KB Memory limit exceeded

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 34980 KB Not a permutation.

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 32664 KB Output is correct
2 Memory limit exceeded 86 ms 262144 KB Memory limit exceeded

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 736 ms 262144 KB Memory limit exceeded

Subtask #20
0 / 5.0

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

Subtask #21
0 / 5.0

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

Subtask #22
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 709 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -