Submission #222134

#	Time	Username	Problem	Language	Result	Execution time	Memory
222134		VEGAnn	Wand (COCI19_wand)	C++14	63 / 70	64 ms	11892 KiB

wand

#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 / 70