Submission #1215555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215555		KindaGoodGames	Newspapers (CEOI21_newspapers)	C++20	0 / 100	0 ms	324 KiB

newspapers

#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

using namespace std;

vector<int> num, low;  
vector<vector<int>> adj;

vector<bool> isArt;

int counter = 0;

void Tarjan(int v, int p){
    num[v] = low[v] = counter++; 
    
    for(auto u : adj[v]){
        if(u == p) continue;
        if(num[u] == -1){
            Tarjan(u,v); 
            low[v] = min(low[v], low[u]);

            if(num[v] <= low[u] && v != 0){
                isArt[v] = true;
            }

        }else{
            low[v] = min(low[v], num[u]);    
        }
    }
}

int mxSz = 1;

void DFS(int v, int p, int sz, vector<bool>& vis){
    if(vis[v]) return;
    mxSz = max(mxSz, sz);
    vis[v] = true;

    for(auto u : adj[v]){
        int nsz = sz+1;
        if(low[v] != low[u]){
            nsz = 1;
        }
        DFS(u,v,nsz,vis);
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    adj.resize(n);
    low = num = vector<int>(n);
    isArt.resize(n);
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    Tarjan(0,0);

    vector<bool> vis(n);
    DFS(0,0,1,vis);

    if(mxSz <= 2){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 8
• Subtask 3: 0 / 80