oj.uz

Submission #1008405

# Submission time Handle Problem Language Result Execution time Memory
1008405 2024-06-26T11:31:53 Z cow123 Newspapers (CEOI21_newspapers) C++14
0 / 100
 0 ms 600 KB 
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = a; i < b;++i)
#define pb emplace_back
using namespace std;
const int maxn = 1005;
vector<int> V[maxn],odp;
int vis[maxn],vis1[maxn],mark[maxn];
void dfs(int v){
    for(auto y : V[v]){
        if(mark[y] == 0 && vis[y] == 0 && V[y].size() > 1){
            vis[y] = 1;
            odp.pb(y);
            odp.pb(v);            
        }
    }
    for(auto y : V[v]){
        if(mark[y] == 1 && vis[y] == 0){
            vis[y] = 1;
            odp.pb(y);
            dfs(y);
        }
    }
}
int d1 = 0;
void dyst(int v){
    for(auto y : V[v]){
        if(vis[y] == 0){
            vis[y] = vis[v] + 1;
            d1 = max(d1,vis[y]);
            dyst(y);
            
        }
    }
}
int main(){
    int n,m;
    cin>>n >>m;
    if(m > n - 1){ //cykl
        cout<<"NIE";
        return 0;
    }
    if(n == 1){
        cout<<"TAK" <<"\n" <<1 <<"\n" <<1;
        return 0;
    }
    if(n == 2){
        cout<<"TAK" <<"\n" <<2 <<"\n" <<1 <<" " <<1;
        return 0;
    }
    
    FOR(i,0,m){
        int x,y;
        cin>>x >>y;
        V[x].pb(y);
        V[y].pb(x);
    }
    FOR(i,1,n + 1){
        if(V[i].size() >= 3){
            FOR(j,0,n + 1){
                vis[j] = 0; 
            }
            vis[i] = 1;
            int cnt = 0;
            for(auto y : V[i]){
                vis[y] = 1;
                  d1 = 0;
                  dyst(y);
                if(d1 >= 3){
                    ++cnt;
                } 
            }
            if(cnt >= 3){ //zakazana czesc 
                cout<<"NIE";
                return 0;
            }
        }
    }
    
    FOR(i,0,n + 1){
        vis[i] = 0;
    }
    d1 = 0;
    int y1 = 0;
    vis[1] = 1;
    dyst(1);
    FOR(i,1,n + 1){
        if(vis[i] == d1){
            y1 = i;
        }
    
    }
    FOR(i,0,n + 1){
        vis[i] = 0;
    }
    d1 = 0;
    vis[y1] = 1;
    dyst(y1);
    FOR(i,1,n + 1){
        if(vis[i] == d1){
            y1 = i;
        }
    }
    FOR(i,0,n + 1){
        vis1[i] = vis[i];
        vis[i] = 0;
    }
    d1 = 0;
    vis[y1] = 1;
    dyst(y1);
    int x2 = 0;
    FOR(i,0,n + 1){
        if(vis[i] + vis1[i] == d1 + 1 && V[i].size() > 1){
            mark[i] = 1;
        }
    }
    FOR(i,0,n + 1){
        vis[i] = 0;
    }
    FOR(i,0,n + 1){
        if(V[i].size() > 1 && mark[i] == 1){
            x2 = i;
        }
    }
    odp.pb(x2);
    vis[x2] = 1;
    dfs(x2);
    cout<<"TAK" <<"\n" <<odp.size() * 2 <<"\n";
    for(auto y : odp){
        cout<<y <<" ";
    }
    for(int i = odp.size() - 1; i >= 0;--i){
        cout<<odp[i] <<" ";
    } 
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Token "TAK" doesn't correspond to pattern "YES|NO"
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Token "TAK" doesn't correspond to pattern "YES|NO"
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 600 KB Token "TAK" doesn't correspond to pattern "YES|NO"
2 Halted 0 ms 0 KB -