Submission #1302372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302372		clue_	Towers (NOI22_towers)	C++20	0 / 100	56 ms	18276 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 5e5 + 5, inf = 1e9, mod = 1e9 + 7, block = 320, lim = 20;

int n, m;
vector <int> adj[N];
int d[N];

namespace sub1 { // duong thang
    int in[N], euler[N];
    int tdfs;
    void dfs1(int u, int par) {
        in[u] = ++tdfs;
        euler[tdfs] = u;
        for (auto v : adj[u]) {
            if (v != par) {
                dfs1(v, u);
            }
        }
    }
    void solve() {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            cnt += (d[i] > -1);
        }
        if (cnt == 0) {
            cout << n << '\n';
            for (int i = 1; i <= n; i++) cout << i << ' ';
        }
        else {
            dfs1(1, 0);
            vector <int> res, res1;
            bool okL = 1, okR = 1;
            for (int i = 1; i <= tdfs; i++) {
                int idx = euler[i];
                if (d[idx] != -1) {
                    if (i > d[i]) {
                        int lst = i - d[i];
                        res.push_back(euler[lst]);
                    }
                    else okL = 0;
                    if (i + d[i] <= tdfs) {
                        int nxt = i + d[i];
                        res1.push_back(euler[nxt]);
                    }
                    else okR = 0;
                }
            }
            sort(res.begin(), res.end());
            res.erase(unique(res.begin(), res.end()), res.end());
            sort(res1.begin(), res1.end());
            res1.erase(unique(res1.begin(), res1.end()), res1.end());
            vector <int> ans;
            if (res.size() == 1 && okL) ans.push_back(res.back());
            if (res1.size() == 1 && okR) ans.push_back(res1.back());
            if (res.size() == 1 && res1.size() == 1 && res.back() == res1.back()) ans.push_back(res.back());
            sort(ans.begin(), ans.end());
            ans.erase(unique(ans.begin(), ans.end()), ans.end());
            cout << ans.size() << '\n';
            for (auto x : ans) cout << x << ' ';
        }
    }
}

namespace sub2 {
    int dist[N];
    void bfs() {
        for (int i = 1; i <= n; i++) dist[i] = inf;
        dist[1] = 0;
        queue <int> q;
        q.push(1);
        while(q.size()) {
            auto u = q.front();
            q.pop();
            for (auto v : adj[u]) {
                if (dist[v] > dist[u] + 1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
    }
    void solve() {
        bfs();
        vector <int> res;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == d[1]) res.push_back(i);
        }
        cout << res.size() << '\n';
        for (auto x : res) cout << x << ' ';
    }
}

namespace sub3 {
    int dist[N];
    void bfs(int id) {
        for (int i = 1; i <= n; i++) dist[i] = inf;
        dist[id] = 0;
        queue <int> q;
        q.push(id);
        while(q.size()) {
            auto u = q.front();
            q.pop();
            for (auto v : adj[u]) {
                if (dist[v] > dist[u] + 1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
    }
    void solve() {
        vector <int> have, nhave;
        for (int i = 1; i <= n; i++) {
            if (d[i] < 0) have.push_back(i);
            else if (d[i] > 0) {
            	nhave.push_back(i);
			}
			else {
				have.push_back(i);
				nhave.push_back(i);
			}
        }
        vector <int> res;
        for (auto x : have) {
            bfs(x);
            bool check = 1;
            for (auto y : nhave) {
                if (d[y] != dist[y]) {
                    check = 0;
                    break;
                }
            }
            if (check) res.push_back(x);
        }
        cout << res.size() << '\n';
        for (auto x : res) cout << x << ' ';
    }
}
int deg[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("cross.inp", "r")) {
        freopen("cross.inp", "r", stdin);
        freopen("cross.out", "w", stdout);
    }
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        deg[u]++, deg[v]++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> d[i];
    bool checksub1 = 1, checksub2 = 1;
    int cntsub1 = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] > 2) checksub1 = 0;
        if (deg[i] == 1) cntsub1++;
        if (i != 1 && d[i] != -1) checksub2 = 0;
    }
    // sub3::solve(); return 0;
    if (checksub1 && cntsub1 == 2) {
        sub1::solve();
        return 0;
    }
    if (checksub2) {
        sub2::solve();
        return 0;
    }
    sub3::solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         freopen("cross.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen("cross.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 31
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19