Submission #718510

#	Time	Username	Problem	Language	Result	Execution time	Memory
718510		Augustyn	Naboj (COCI22_naboj)	C++17	110 / 110	152 ms	15128 KiB

naboj

#include<iostream>
#include<vector>
using namespace std;
int sw()
{
    int ret=0,wcz=getchar_unlocked();
    while(wcz<'0'||wcz>'9')
        wcz=getchar_unlocked();
    while(wcz>='0'&&wcz<='9')
    {
        ret=ret*10+wcz-'0';
        wcz=getchar_unlocked();
    }
    return ret;
}
int n,m;
vector<int>*pol;
bool *juzodw,*terodw;
int *stp_wch,*odp,iter;
bool dfs(int ter)
{
    juzodw[ter]=1;
    terodw[ter]=1;
    for(auto i:pol[ter])
    {
        if(terodw[i]==1)
            return 1;
        if(juzodw[i]==0)
            if(dfs(i))
                return 1;
    }
    terodw[ter]=0;
    odp[++iter]=ter;
    return 0;
}
int main()
{
    n=sw();m=sw();
    pol=new vector<int>[n+1];
    juzodw=new bool[n+1];
    terodw=new bool[n+1];
    odp=new int[n+1];
    stp_wch=new int[n+1];
    while(m)
    {
        --m;
        int a,b;
        a=sw();b=sw();
        pol[b].push_back(a);
        stp_wch[a]++;
    }
    for(int i=1;i<=n;++i)
        if(stp_wch[i]==0)
            if(dfs(i))
            {
                printf("-1");
                return 0;
            }
    if(iter!=n)
    {
        printf("-1");
        return 0;
    }
    printf("%d\n",n);
    for(int i=1;i<=n;++i)
        printf("%d 0\n",odp[i]);
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 25 / 25
• Subtask 3: 70 / 70