oj.uz

Submission #313372

# Submission time Handle Problem Language Result Execution time Memory
313372 2020-10-15T21:59:04 Z Ahmad_Hasan Ronald (COCI17_ronald) C++17
120 / 120
 43 ms 3576 KB 
#include <bits/stdc++.h>

using namespace std;
/**
struct st1d{
    int sz=2;
    vector<int>vls;
    void init(int n){
        while(sz<n) sz*=2;
        vls=vector<int>(2*sz,0);
    }

    void update(int i,int vl,int x,int lx,int rx){

        ///cout<<lx<<' '<<rx<<'\n';
        if(rx==lx){
            vls[x]+=vl;
            return;
        }
        int mid=(lx+rx)/2;
        if(i<=mid)
        update(i,vl,2*x,lx,mid);
        else
        update(i,vl,2*x+1,mid+1,rx);
        vls[x]=vls[2*x]+vls[2*x+1];
    }

    void update(int i,int vl){
        update(i,vl,1,0,sz-1);
    }

    int get(int l,int r,int x,int lx,int rx){
        if(rx<l||lx>r) return 0;
        if(lx>=l&&rx<=r){
            return vls[x];
        }
        int mid=(lx+rx)/2;
        return get(l,r,2*x,lx,mid)+get(l,r,2*x+1,mid+1,rx);
    }

    int get(int l,int r){
        return get(l,r,1,0,sz-1);
    }
    void print(){
        for(int i=1;i<=2*sz;i*=2){
            for(int j=i/2;j<i;j++)
                cout<<vls[j]<<' ';
            cout<<'\n';
        }
    }

};
struct st2d{
    int sz=2;
    vector<st1d>vls;
    void init(int n,int m){
        while(sz<n) sz*=2;
        st1d tmp;
        tmp.init(m);
        vls=vector<st1d>(2*sz,tmp);
    }

    void update(int ix,int iy,int vl,int x,int lx,int rx){

        ///cout<<lx<<' '<<rx<<'\n';
        if(rx==lx){
            vls[x].update(iy,vl);
            return;
        }
        int mid=(lx+rx)/2;
        if(ix<=mid)
        update(ix,iy,vl,2*x,lx,mid);
        else
        update(ix,iy,vl,2*x+1,mid+1,rx);
        vls[x].update(iy,vl);
    }

    void update(int ix,int iy,int vl){
        update(ix,iy,vl,1,0,sz-1);
    }

    int get(int xl,int xr,int yl,int yr,int x,int lx,int rx){
        if(rx<xl||lx>xr) return 0;
        if(lx>=xl&&rx<=xr){
            return vls[x].get(yl,yr);
        }
        int mid=(lx+rx)/2;
        return get(xl,xr,yl,yr,2*x,lx,mid)+get(xl,xr,yl,yr,2*x+1,mid+1,rx);
    }

    int get(int xl,int xr,int yl,int yr){
        return get(xl,xr,yl,yr,1,0,sz-1);
    }
    void print(){
        for(int i=1;i<=2*sz;i*=2){
            for(int j=i/2;j<i;j++)
                cout<<vls[j].get(0,sz-1)<<' ';
            cout<<'\n';
        }
    }

};
**/


vector<vector<int > >adj;
vector<int>vis;
int f=0;

void dfs(int cr,int trg=-1){
    vis[cr]=1;
    if(trg!=-1&&adj[cr].size()!=trg){
        f=1;
        return;
    }
    if(f)
        return;
    for(int i=0;i<adj[cr].size();i++){
        if(!vis[adj[cr][i]])
            dfs(adj[cr][i],adj[cr].size());
    }

}



int main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(0);
    int n,e;
    cin>>n>>e;
    adj.resize(n);
    vis=vector<int>(n,0);
    for(int i=0;i<e;i++){
        int x,y;
        cin>>x>>y;
        x--;  y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        if(!vis[i])
            dfs(i),cnt++;
    }
    if(f||cnt>2)
    cout<<"NE"<<'\n';
    else
    cout<<"DA"<<'\n';

    return 0;
}

/***
1 4
100 100 100 100

*/

Compilation message

ronald.cpp: In function 'void dfs(int, int)':
ronald.cpp:112:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |     if(trg!=-1&&adj[cr].size()!=trg){
      |                 ~~~~~~~~~~~~~~^~~~~
ronald.cpp:118:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int i=0;i<adj[cr].size();i++){
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 11 ms 1152 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 3 ms 512 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 29 ms 2688 KB Output is correct
4 Correct 43 ms 3576 KB Output is correct