QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#142632 | #6526. Canvas | BUET_POTATOES# | RE | 1ms | 3596kb | C++20 | 4.2kb | 2023-08-19 15:21:14 | 2023-08-19 15:21:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
void solv(){
int n,m;
cin>>n>>m;
vector< vector<pii> >g1(n+1);
vector<int>age, pore;
vector<pii>lr(m+1), xy(m+1);
vector<int>vis(n+1);
for(int i=1; i<=m; i++){
int l,r,x,y;
cin>>l>>x>>r>>y;
lr[i] = {l,r};
xy[i] = {x,y};
if(x==1 and y==1) age.push_back(i);
if(x==2 and y==2){
pore.push_back(i);
vis[l] = vis[r] = 2;
}
if(x!=y){
if(x==1){
g1[l].emplace_back(r, i);
}
else{
g1[r].emplace_back(l, i);
}
}
}
/// age, baad, majhe, pore
vector<int>baad;
vector<int>majhe;
auto dfs = [&](auto &dfs, int u) -> void {
vis[u] = 1;
for(auto [v,idx] : g1[u]){
if(vis[v]) {
baad.push_back(idx);
}
else{
dfs(dfs, v);
majhe.push_back(idx);
}
}
};
for(int i=1; i<=n; i++){
if(vis[i]==2){
for(auto [v,idx] : g1[i]){
if(vis[v]){
baad.push_back(idx);
}
else{
dfs(dfs, v);
majhe.push_back(idx);
}
}
}
}
vector< vector<pii> >g(n+1);
vector< vector<pii> >grev(n+1);
for(int i=1; i<=n; i++){
for(auto [v,idx] : g1[i]) {
if(vis[i] and vis[v]) continue;
if(!vis[i] and !vis[v]){
g[i].emplace_back(v, idx);
grev[v].emplace_back(i, idx);
// cout<<"ej added "<<i<<" -> "<<v<<endl;
}
else if(!vis[i] and vis[v]){
baad.push_back(idx);
}
}
}
fill(vis.begin(), vis.end(), 0);
vector<int>order;
vector<int>which(n+1);
int cc = 0;
auto dfs1 = [&](auto &dfs1, int u) -> void {
if(vis[u]) return;
vis[u] = true;
for(auto [v,idx] : g[u]){
dfs1(dfs1, v);
}
order.push_back(u);
};
auto dfs2 = [&] (auto &dfs2, int u, int id) -> void {
if(vis[u]) return;
vis[u] = true;
for(auto [v,idx] : grev[u]){
dfs2(dfs2, v, id);
}
which[u] = id;
};
for(int i=1; i<=n; i++){
if(!vis[i]){
dfs1(dfs1, i);
}
}
// cout<<"order = ";
reverse(order.begin(), order.end());
// for(int x : order){
// cout<<x<<" ";
// }
// cout<<endl;
fill(vis.begin(), vis.end(), 0);
for(int u : order){
if(vis[u]) continue;
dfs2(dfs2, u, ++cc);
}
//
// for(int i=1; i<=n; i++){
// cout<<" comp of "<<i<<" = "<<which[i]<<endl;
// }
vector<int>indeg(cc+1);
for(int i=1; i<=n; i++) {
for(auto [v,idx] : g[i]){
indeg[ which[v] ]++;
}
}
auto dfs4 = [&](auto &dfs4, int u) -> void {
vis[u] = 1;
for(auto [v,idx] : g[u]){
if(vis[v]) {
baad.push_back(idx);
}
else{
dfs4(dfs4, v);
majhe.push_back(idx);
}
}
};
fill(vis.begin(), vis.end(), 0);
for(int i=1; i<=n; i++){
if( indeg[ which[i] ] == 0 and !vis[i]){
dfs4(dfs4, i);
}
}
vector<int>serial = age;
for(int x : baad) serial.push_back(x);
for(int x : majhe) serial.push_back(x);
for(int x : pore) serial.push_back(x);
vector<int>arr(n+1);
for(int idx : serial){
arr[ lr[idx].first ] = xy[idx].first;
arr[ lr[idx].second ] = xy[idx].second;
}
cout<< accumulate(arr.begin(), arr.end(), 0)<<"\n";
for(int idx : serial) cout<<idx<<" ";
cout<<"\n";
// cout<<endl;
assert(serial.size()==m);
}
/*
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
*/
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int tc;
cin>>tc;
while(tc--){
solv();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3596kb
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 2 1 3 5 2 1
result:
ok Correct. (2 test cases)
Test #2:
score: -100
Dangerous Syscalls
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