QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#564516	#4243. Good Coloring	rotcar07	WA	52ms	5740kb	C++20	975b	2024-09-15 08:35:58	2024-09-15 08:35:59

Judging History

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

[2024-09-15 08:35:59]
评测

测评结果：WA
用时：52ms
内存：5740kb

查看

[2024-09-15 08:35:58]
提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int N=3e5+5;
int n,m,k,c[N];
vector<int> e[N];
vector<int> w[N];
int dp[N];
inline void solve(){
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++) w[i].clear();
    for(int i=1;i<=n;i++) cin>>c[i],w[c[i]].push_back(i),e[i].clear(),dp[i]=0;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        if(c[u]>c[v]) swap(u,v);
        e[v].push_back(u);
    }
    int mx=0;
    for(int i=1;i<=k;i++){
        for(auto x:e[i]) dp[i]=max(dp[i],dp[x]);
        dp[i]++;mx=max(mx,dp[i]);
    }
    cout<<mx<<' ';for(int i=1;i<=n;i++) cout<<dp[i]<<' ';cout<<'\n';
    vector<int> sb;
    int w=0;for(int i=1;i<=n;i++) if(dp[i]==mx){w=i;break;}
    cout<<w<<' ';
    for(int i=mx-1;i>=1;i--){
        for(auto x:e[w]) if(dp[x]==i){w=x;break;}
        cout<<w<<" ";
    }
    cout<<'\n';
}
int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--) solve();
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3680kb

input:

output:

result:

ok good job (2 test cases)

Test #2:

score: -100

Wrong Answer

time: 52ms

memory: 5740kb

input:

50000
5 7 5
5 2 3 1 5
4 3
3 1
5 2
5 4
5 3
2 4
4 1
6 5 5
1 1 4 5 5 2
2 3
3 5
6 1
2 4
1 5
7 5 6
4 6 3 5 6 5 3
5 4
5 6
7 2
1 2
3 6
7 7 4
3 4 2 1 3 4 1
6 7
3 4
3 6
3 5
6 1
2 3
2 4
5 6 5
3 3 4 4 1
4 5
2 3
5 2
3 1
4 2
5 1
6 6 3
2 3 2 2 1 1
2 6
3 5
2 5
6 3
4 5
4 6
7 5 2
1 2 1 1 2 2 1
5 4
5 3
7 5
1 2
3 2
7 ...

output:

2 1 1 1 1 2 
5 2 
3 1 1 2 2 3 0 
5 3 2 
2 1 2 1 1 2 2 0 
2 1 
1 1 1 1 1 0 0 0 
1 
2 1 1 2 2 1 
3 2 
1 1 1 1 0 0 0 
1 
2 1 2 0 0 0 0 0 
2 1 
2 1 1 1 1 1 2 1 
6 4 
3 1 2 1 1 3 
5 2 1 
2 1 1 1 2 2 1 
4 1 
2 1 1 1 1 1 2 
6 2 
2 1 1 1 1 2 0 0 
5 2 
3 1 1 1 2 2 3 0 
6 4 2 
3 1 1 1 2 3 0 0 
5 4 3 
1 1 1 1 ...

result:

wrong answer invalid coloring: the colors of vertex 1 and 3 are the same (test case 1)