Submission #1155091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155091		ace5	Newspapers (CEOI21_newspapers)	C++20	8 / 100	0 ms	584 KiB

newspapers

#include <bits/stdc++.h>

using namespace std;
/*
typedef long long ll;

mt19937 rnd(228);

const int maxn = 300005;
const int sqr = 550;
const int pos1 = 150002;
const int maxq = 50005;

ll val[maxn];
int bl[maxn];
ll a[maxn];
int posex[maxn];
vector<pair<int,int>> ex(maxn);
int L = 0,R = -1;
int kel = 0;

struct block
{
    block(int _l,int _r,ll _sum,ll _wsum,ll _ans){l = _l,r = _r;sum = _sum;wsum = _wsum;ans = _ans;};
    block(){};
    int l,r;
    ll sum;
    ll wsum;
    ll ans;
    void upd()
    {
        sum = 0;
        wsum = 0;
        ans = 0;
        for(int j = l;j <= r;++j)
        {
            ans += val[j] * (sum * (j-l+2) - wsum) + (val[j] * (val[j] + 1) / 2);
            sum += val[j];
            wsum += (j-l+1) * val[j];
        }
    }
};

block mrg(block a,block b)
{
    block ans;
    ans.sum = a.sum + b.sum;
    ans.wsum = a.wsum + b.wsum + b.sum * (a.r-a.l+1);
    ans.ans = a.ans + b.ans + a.sum * (b.wsum + b.sum) + (a.sum * (a.r-a.l+1) - a.wsum) * b.sum;
    ans.l = a.l;
    ans.r = b.r;
    return ans;
}

block decomp[sqr];


void add_dec(int i,int x)
{
   // cout << "adding: " << x << " to " << i << endl;
    val[i] += x;
    decomp[bl[i]].sum += x;
    decomp[bl[i]].wsum += x * (i - bl[i]*sqr + 1);
    decomp[bl[i]].ans += x *
    decomp[bl[i]].upd();
   // cout << decomp[bl[i]].ans << ' ';
}

ll get(int l,int r)
{
    block ans = block(0,-1,0,0,0);
    while(l < r)
    {
        if(l % sqr != 0 || l + sqr - 1 > r)
        {
            ans = mrg(ans,block(l,l,val[l],val[l],val[l] * (val[l]+1) / 2));
            l++;
        }
        else
        {
            ans = mrg(ans,decomp[bl[l]]);
            l += sqr;
        }
    }
    return ans.ans;
}

int get_pos(int tpos,int sz)
{
    int d = (sz-tpos)/2;
    return pos1 + (sz%2 == tpos%2 ? -d : d);
}

void add(int el)
{
    //cout << el << "+\n";
    int tv = ex[posex[el]].first;
    int tpos = posex[el];//(upper_bound(ex.end()-kel-1,ex.end(),make_pair(tv,maxn+5))-ex.begin()-1);
    //cout << tpos << ' ';
    add_dec(get_pos(tpos,ex.size()),1);
    if(!ex[tpos].first)
        kel++;
    ex[tpos].first ++;
    int el2 = ex[tpos].second;
    swap(ex[tpos].second,ex[posex[el]].second);
    swap(posex[el],posex[el2]);
}
void sub(int el)
{
    //cout << el << "-\n";
    int tv = ex[posex[el]].first;
    int tpos = posex[el];//(lower_bound(ex.end()-kel-1,ex.end(),make_pair(tv,0))-ex.begin());
   // cout << tpos << ' ';
    add_dec(get_pos(tpos,ex.size()),-1);
    ex[tpos].first --;
    if(!ex[tpos].first)
        kel--;
    int el2 = ex[tpos].second;
    swap(ex[tpos].second,ex[posex[el]].second);
    swap(posex[el],posex[el2]);
}

ll res[maxq];

struct query
{
    query(int _l,int _r,int _i){l = _l;r = _r;i = _i;};
    query(){};
    int l,r,i;
    bool operator < (const query & oth){return (l/sqr != oth.l/sqr ? l/sqr < oth.l/sqr : r < oth.r);};
};

vector<query> ev;

void go_ll()
{
    L--;
    add(a[L]);
}
void go_lr()
{
    sub(a[L]);
    L++;
}
void go_rr()
{
    R++;
    add(a[R]);
}
void go_rl()
{
    sub(a[R]);
    R--;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    for(int i = 0;i < maxn;++i)
    {
        ex[i].second = i;
        posex[i] = i;
        val[i] = 0;
        bl[i] = i/sqr;
    }
    for(int i = 0;i < sqr;++i)
        decomp[i] = block(i*sqr,(i+1)*sqr-1,0,0,0);
    int n = 300000,q = 50000;
    //cin >> n >> q;
    for(int i = 0;i < n;++i)
    {
        a[i] = rnd()%300000+1;
        //cin >> a[i];
    }
    for(int i = 0;i < q;++i)
    {
        int l = rnd()%n+1,r = rnd()%n+1;
        if(l > r)
            swap(l,r);
        //cin >> l >> r;
        l--;
        r--;
        ev.push_back(query(l,r,i));
    }
    sort(ev.begin(),ev.end());
    for(int i = 0;i < ev.size();++i)
    {
        if(i != 0 && ev[i].l/sqr != ev[i-1].l/sqr)
        {
            cout << ev[i].l << ' ' << ev[i].r << endl;
        }
       // cout << ev[i].r << ' ';
        int tl = ev[i].l;
        int tr = ev[i].r;
        while(L > tl)
        {
            go_ll();
        }
        while(R < tr)
        {
            go_rr();
        }
        while(L < tl)
        {
            go_lr();
        }
        while(R > tr)
        {
            go_rl();
        }
        res[ev[i].i] = get(0,maxn-1);
    }
    for(int i= 0 ;i < q;++i)
    {
        cout << res[i] << "\n";
    }
    return 0;
}*/

vector<vector<int>> g;
bool cyc = 0;
vector<int> vis;

void dfs1(int v,int p)
{
    vis[v] = 1;
    for(auto u:g[v])
    {
        if(!vis[u])
            dfs1(u,v);
        else if(u != p)
            cyc = 1;
    }
    return ;
}
pair<int,int> dfs2(int v,int p)
{
    pair<int,int> ans  ={v,0};
    for(auto u:g[v])
    {
        if(u != p)
        {
            pair<int,int> ne = dfs2(u,v);
            if(ne.second + 1 > ans.second)
            {
                ans = {ne.first,ne.second+1 };
            }
        }
    }
    return ans;
}
vector<int> path;

bool dfs3(int v,int p,int to)
{
    path.push_back(v);
    if(v == to)
    {
        return true;
    }
    for(auto u:g[v])
    {
        if(u != p)
        {
            if(dfs3(u,v,to))
                return true;
        }
    }
    path.pop_back();
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    g.resize(n);
    vis.resize(n);
    for(int j = 0;j < m;++j)
    {
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(0,-1);
    if(cyc)
    {
        cout << "NO\n";
        return 0;
    }
    else
    {
        int st = dfs2(0,-1).first;
        int fn = dfs2(st,-1).first;
        dfs3(st,-1,fn);
        vector<bool> isin(n);
        for(int j = 0;j < path.size();++j)
        {
            isin[j] = 1;
        }
        int no = 0;
        for(int j = 0;j < n;++j)
        {
            if(!isin[j])
            {
                if(g[j].size() != 1)
                {
                    for(auto u:g[j])
                    {
                        if(!isin[u] && g[u].size() > 1)
                        {
                            no = 1;
                        }
                    }
                }
            }
        }
        if(no)
        {
            cout << "NO\n";
        }
        else
        {
            cout << "YES\n";
            if(n == 1)
            {
                cout << "1\n1";
                return 0;
            }
            else if(n == 2)
            {
                cout << "2\n1 1\n";
                return 0;
            }
            vector<int> ans;
            for(int i = 1;i+1 < path.size();++i)
            {
                ans.push_back(path[i]);
                for(auto u:g[path[i]])
                {
                    if(!isin[u] && g[u].size() > 1)
                    {
                        ans.push_back(u);
                        ans.push_back(path[i]);
                    }
                }
            }
            for(int j = path.size()-2;j > 0;--j)
                ans.push_back(path[j]);
            cout << ans.size() << "\n";
            for(auto c:ans)
                cout << c+1 << ' ';
        }
    }
}

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