QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#429184#6526. Canvasdnialh#WA 1ms5644kbC++206.2kb2024-06-02 02:44:452024-06-02 02:44:45

Judging History

你现在查看的是最新测评结果

  • [2024-06-02 02:44:45]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5644kb
  • [2024-06-02 02:44:45]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define F0R(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i <= b; i++)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define FORd(i,a,b) for (int i = (b); i >= (a); i--)
#define trav(a, x) for (auto& a : x)
#define rep(i, a, b) for(int i = a; i < (b); ++i)

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

const char nl = '\n';
const int MAX_N = 100011;
const ll INF = (1<<29) + 123;
const ll MOD = 1000000007; // 998244353
const ld PI = 4*atan((ld)1);

template <typename T> bool ckmin(T& a, const T& b) { return a > b ? a=b, 1 : 0; }
template <typename T> bool ckmax(T& a, const T& b) { return b > a ? a=b, 1 : 0; }

/**** Credit to chatgpt 4.0 ****/

// Stream operator for std::pair
template<typename T1, typename T2>
ostream& operator<<(ostream &out, const pair<T1, T2> &v) {
    out << "(" << v.first << ", " << v.second << ")"; 
    return out;
}

// Trait to check if a type is iterable
template<typename T, typename = void>
struct is_iterable : false_type {};

template<typename T>
struct is_iterable<T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {};

// Stream operator for iterable types excluding std::string
template<typename TT>
typename enable_if<is_iterable<TT>::value && !is_same<TT, string>::value, ostream&>::type
operator<<(ostream& out, const TT& c) {
    out << "{ ";
    for (const auto& x : c) out << x << " ";
    out << "}"; 
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, std::stack<T> container) {
    std::vector<T> elements;
    while (!container.empty()) {
        elements.push_back(container.top());
        container.pop();
    }
    std::reverse(elements.begin(), elements.end()); // Reverse to maintain order
    return out << elements;
}

template<typename T>
ostream& operator<<(ostream& out, std::queue<T> container) {
    std::vector<T> elements;
    while (!container.empty()) {
        elements.push_back(container.front());
        container.pop();
    }
    return out << elements;
}

// Helper function to print std::priority_queue
template<typename T, typename Container, typename Compare>
ostream& operator<<(ostream& out, std::priority_queue<T, Container, Compare> pq) {
    out << "{";
    while (!pq.empty()) {
        out << " " << pq.top();
        pq.pop();
    }
    out << " }";
    return out;
}

#ifdef DBG
void dbg_out() { cerr << endl; }

template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
}

#define dbg(...) cerr << #__VA_ARGS__ << ":", dbg_out(__VA_ARGS__);
#define dbg_array(a, n) cerr << #a << ": { "; for(int i = 0; i < n; i++) cerr << a[i] << " "; cerr << "}\n";
#else
#define dbg(...)
#define dbg_array(a, n)
#endif

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

const int MX = 3e5+5;

bool vis[MX];
bool sources[MX];

vi val, comp, z, cont;
int Time, ncomps;
int n, m;
template<class G, class F> int dfs(int j, G& g, F& f) {
	int low = val[j] = ++Time, x; z.push_back(j);
	for (auto e : g[j]) if (comp[e.f] < 0)
		low = min(low, val[e.f] ?: dfs(e.f,g,f));

	if (low == val[j]) {
		do {
			x = z.back(); z.pop_back();
			comp[x] = ncomps;
			cont.push_back(x);
		} while (x != j);
		f(cont); cont.clear();
		ncomps++;
	}
	return val[j] = low;
}
template<class G, class F> void scc(G& g, F f) {
	val.assign(n, 0); comp.assign(n, -1);
	Time = ncomps = 0;
	rep(i,0,n) if (comp[i] < 0) dfs(i, g, f);
}

vpi gr[MX], rgr[MX]; // graph and reverse graph

bool seen[MX];
vi cur;
void dfs2(int v) {
    if (seen[v]) return;
    seen[v] = 1;
    trav(e, gr[v]) {
        cur.pb(e.s);
        dfs2(e.f);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) {
        cin >> n >> m;
        F0R(i, n) vis[i] = 0;
        F0R(i, n) sources[i] = 0; 
        F0R(i, n) seen[i] = 0;
        F0R(i, n) gr[i].clear();
        F0R(i, n) rgr[i].clear();
        vi start, end;
        F0R(i, m) {
            int l, x, r, y; cin >> l >> x >> r >> y;
            l--; x--; r--; y--;
            if (x&&y) {
                end.pb(i);
                sources[l] = sources[r] = 1;
            } else if (x&&!y) {
                gr[r].pb({l, i});
                rgr[l].pb({r, i});
            } else if (!x&&y) {
                gr[l].pb({r, i});
                rgr[r].pb({l, i});
            } else {
                start.pb(i);
            }
            vis[l] = vis[r] = 1;
        }
        int ans = 0;
        F0R(i, n) if (vis[i]) ans+=2;
        scc(gr, [&](vi& v) {
            assert(sz(v));
            if (sz(v) == 1 && !vis[v[0]]) {
                return;
            }
            dbg("size", sz(v), "comp label", comp[v[0]]);
            dbg("comp", cont);
            // check if there's any sources in this component or if it has any parents
            bool ok = 0;
            trav(u, v) {
                if (sz(rgr[u]) > 0 || sources[u]) {
                    ok = 1;
                    break;
                }
            }
            dbg(ok);
            if (!ok) {
                ans--;
                // pick someone random to be a source here
                sources[v[0]] = 1;
            }
        });
        cout << ans << nl;
        // now we just compute the ordering by dfs-ing from every source and reversing the vector
        vi order = start;
        F0R(i, n) {
            if (seen[i] || !sources[i]) continue;
            cur.clear();
            dfs2(i);
            dbg(i, cur);
            reverse(all(cur));
            order.insert(order.end(), cur.begin(), cur.end());
        }
        order.insert(order.end(), end.begin(), end.end());
        trav(o, order) cout << o+1 << " "; cout << nl;
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5644kb

input:

2
4 4
1 1 2 2
3 2 4 1
1 2 3 2
2 1 4 1
4 2
3 2 4 1
1 2 3 1

output:

7
4 1 2 3 
5
2 1 

result:

ok Correct. (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 5596kb

input:

1
10 13
1 1 2 2
2 1 3 2
1 2 3 1
3 1 4 2
4 1 5 2
5 1 6 2
4 2 6 1
7 1 8 2
8 1 9 2
7 2 9 1
5 2 9 1
8 2 10 2
1 1 10 1

output:

20
13 5 7 6 11 8 10 9 12 

result:

wrong output format Unexpected end of file - int32 expected (test case 1)