oj.uz

Submission #222095

# Submission time Handle Problem Language Result Execution time Memory
222095 2020-04-12T06:22:37 Z Vimmer Wand (COCI19_wand) C++14
70 / 70
 48 ms 4728 KB 
#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100005
#define MOD ll(998244353)

using namespace std;

typedef long long ll;

typedef long double ld;


vector <int> g[N];

bool mk[N];

void dfs(int v, int p)
{
    if (p != -1) mk[v] = 1;

    bool f = 0;


    for (auto it : g[v])
    {
        if (mk[it]) continue;

        f = 1;

        dfs(it, v);
    }

    if (!f) mk[v] = 1;
}
int main()
{

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;

    cin >> n >> m;

    if (n == 1) mk[1] = 1;

    for (int i = 0; i < m; i++)
    {
        int x, y;

        cin >> x >> y;

        g[y].pb(x);
    }

    dfs(1, -1);

    for (int i = 1; i <= n; i++) cout << mk[i];
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 7 ms 2688 KB Output is correct
3 Correct 48 ms 4600 KB Output is correct
4 Correct 41 ms 4600 KB Output is correct
5 Correct 37 ms 4600 KB Output is correct
6 Correct 42 ms 4728 KB Output is correct
7 Correct 37 ms 4600 KB Output is correct
8 Correct 41 ms 4728 KB Output is correct
9 Correct 39 ms 4728 KB Output is correct
10 Correct 41 ms 4728 KB Output is correct