oj.uz

Submission #126578

# Submission time Handle Problem Language Result Execution time Memory
126578 2019-07-08T06:29:20 Z _Samir Ronald (COCI17_ronald) C++17
120 / 120
 195 ms 15588 KB 
//github.com/nya-nya-meow/CompetitiveProgramming/blob/master/CSES/CSES%201112%20-%20Substrings.cpp
#include<bits/stdc++.h>
#define pi 3.141592654
#define forr(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define input ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;
typedef pair<double,double>pdd;
typedef long long  ll;
typedef pair<ll, ll>pii;
typedef complex<double> point;
//int x[8]={1,0,0,-1,-1,-1,1,1};
//int y[8]={0,1,-1,0,-1,1,-1,1};

const double EPS= 1e-8;
const int N = 1e5+5, M = 2e5+5, OO = 0x3f3f3f3f;

int n,m,vis[2005],id,ck[5000000];
vector<int>a[2005];
void dfs(int u)
{
    vis[u]=id;
    for(auto v:a[u])
        if(vis[v]==-1)dfs(v);
}
 int main()
{

input;
cin>>n>>m;
int u,v;
forr(i,1,m)
{
    cin>>u>>v;
    a[u].push_back(v);
    a[v].push_back(u);
}
memset(vis,-1,sizeof vis);
forr(i,1,n)
{
    if(vis[i]==-1)
    {
        id++;
        dfs(i);
    }
}
set<pair<int,int>>c1,c2;
int cnt1=0,cnt2=0;
forr(i,1,n)
{
    if(vis[i]==1){
       cnt1++;
       for(auto v:a[i])
         c1.insert({min(i,v),max(i,v)});}
    else if(vis[i]==2){
       cnt2++;
       for(auto v:a[i])
         c2.insert({min(i,v),max(i,v)});}
}
for(int i=1;i<=2000;i++)ck[i]=i*(i-1)/2;
if((id==1&&ck[cnt1]==(int)c1.size())||(id==2&&ck[cnt1]==(int)c1.size()&&ck[cnt2]==(int)c2.size()))cout<<"DA"<<endl;
else cout<<"NE"<<endl;
return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
15.0 / 15.0

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

Subtask #5
15.0 / 15.0

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

Subtask #6
15.0 / 15.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1016 KB Output is correct
2 Correct 41 ms 4228 KB Output is correct
3 Correct 15 ms 1784 KB Output is correct
4 Correct 10 ms 1276 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 32 ms 2936 KB Output is correct
3 Correct 158 ms 10380 KB Output is correct
4 Correct 195 ms 15588 KB Output is correct