Submission #1226815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226815		HishamAlshehri	Traffic (CEOI11_tra)	C++20	0 / 100	679 ms	193980 KiB

tra

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
// using namespace __gnu_pbds;
 
#define int long long
#define mod 1000000007
#define base 7001
#define base2 757
#define F first
#define S second
// #define pi acos(-1)
#define double long double
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
// #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,sse3,sse4,avx")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

constexpr int maxn = 3000005;
const int N = 1 << (int)(ceil(log2(maxn)));

int n, m, a, b, east[maxn], west[maxn], ans[maxn];
vector<int> adj[maxn][2];
vector<array<int, 3>> cords;
bool vis[maxn], vis2[maxn], vis3[maxn], mark[maxn];

void dfs(int v, bool f) {
    vis[v] = 1;
    for (int u : adj[v][f]) {
        if (!vis[u]) dfs(u, f);
    }
}

void dfsmn(int v, int s) {
    vis3[v] = 1;

    for (int u : adj[v][1]) {
        if (!vis3[u]) dfsmn(u, s);
    }

    ans[v] += -s;
}

void dfsmx(int v, int s) {
    vis2[v] = 1;

    for (int u : adj[v][1]) {
        if (!vis2[u]) dfsmx(u, s);
    }
    
    ans[v] += s;
}

void calc() {
    sort(cords.begin(), cords.end());

    for (auto [y, x, i] : cords) {
        if (!i) continue;
        if (east[i] && !vis3[i]) dfsmn(i, east[i]);
    }

    reverse(cords.begin(), cords.end());

    for (auto [y, x, i] : cords) {
        if (!i) continue;
        if (east[i] && !vis2[i]) dfsmx(i, east[i]);
    }
}

signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m >> a >> b;

    int cnt = 0;
    cords.push_back({0, 0});
    for (int i = 1; i <= n; i++) {
        int x, y; cin >> x >> y;
        cords.push_back({y, x, i});
        if (x == a) {
            cnt++;
            east[i] = cnt;
        }
        if (!x) west[i] = 1;
    }

    for (int i = 0; i < m; i++) {
        int u, v, d; cin >> u >> v >> d;
        if (d % 2) {
            adj[u][0].push_back(v);
            adj[v][1].push_back(u);
        }
        else {
            adj[u][0].push_back(v);
            adj[v][0].push_back(u);
            adj[u][1].push_back(v);
            adj[v][1].push_back(u);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i] && west[i]) dfs(i, 0);
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i] && east[i]) vis2[i] = vis3[i] = mark[i] = 1;
    }

    memset(vis, 0, sizeof vis);

    for (int i = 1; i <= n; i++) {
        if (!vis[i] && east[i]) dfs(i, 1);
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i] && west[i]) {
            vis2[i] = vis3[i] = mark[i] = 1;
        }
    }

    calc();

    for (auto [y, x, i] : cords) {
        if (west[i]) cout << ans[i] + (mark[i] ? 0 : 1) << '\n';
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 8
• Subtask 5: 0 / 8
• Subtask 6: 0 / 8
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9