oj.uz

Submission #222134

# Submission time Handle Problem Language Result Execution time Memory
222134 2020-04-12T07:36:45 Z VEGAnn Wand (COCI19_wand) C++14
63 / 70
 64 ms 11892 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 100100;
const ll OO = 1e18;
const ld E = 1e-9;
vector<int> g[N], gr[N], ts;
int n, m, comp[N], kol = 0, siz[N], ans = 0;
bool mrk[N];

void top_sort(int v){
    if (mrk[v]) return;
    mrk[v] = 1;

    for (int u : g[v])
        top_sort(u);

    ts.PB(v);
}

void dfs(int v){
    if (comp[v] != -1) return;
    comp[v] = kol;
    siz[kol]++;

    for (int u : gr[v])
        dfs(u);
}

void last_dfs(int v){
    if (mrk[v]) return;
    mrk[v] = 1;

    for (int u : g[v])
        last_dfs(u);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("in.txt","r",stdin);

    cin >> n >> m;

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

        g[y].PB(x);
        gr[x].PB(y);
    }

    for (int i = 0; i < n; i++)
        if (!mrk[i])
            top_sort(i);

    reverse(all(ts));
    fill(comp, comp + n, -1);

    for (int v : ts)
        if (comp[v] == -1){
            dfs(v);
            kol++;
        }

    fill(mrk, mrk + n, 0);

    for (int v = 0; v < n; v++)
        if (comp[v] == comp[0])
            last_dfs(v);

    mrk[0] = bool(siz[comp[0]] > 1);

    for (int i = 0; i < n; i++)
        cout << mrk[i];

    return 0;
}

Subtask #1
63.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 59 ms 11376 KB Output is correct
4 Correct 57 ms 11384 KB Output is correct
5 Correct 59 ms 11504 KB Output is correct
6 Correct 64 ms 11632 KB Output is correct
7 Correct 57 ms 11376 KB Output is correct
8 Correct 62 ms 11632 KB Output is correct
9 Incorrect 63 ms 11892 KB Output isn't correct
10 Correct 62 ms 11892 KB Output is correct