QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #134802 | #4162. 所驼门王的宝藏 | osky123456 | 0 | 1ms | 13708kb | C++14 | 2.6kb | 2023-08-04 23:21:15 | 2023-08-04 23:21:18 |
Judging History
answer
// Problem: P2403 [SDOI2010] 所驼门王的宝藏
// URL: https://www.luogu.com.cn/problem/P2403
#include<bits/stdc++.h>
#define mp make_pair
const int maxn = 1e5+7;
using namespace std;
int n,r,c;
int head[maxn],cnt;
struct node{
int v,next;
}edge[maxn<<1];
int _head[maxn],_cnt;
struct _node{
int v,next;
}_edge[maxn<<1];
void add(int u,int v){
if(u==v) return ;
edge[++cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
void _add(int u,int v){
_edge[++cnt].v=v;
_edge[cnt].next=_head[u];
_head[u]=cnt;
}
int x[maxn],y[maxn],opt[maxn];
vector<int> a[maxn],b[maxn];
map<pair<int,int>,int> vis;
int dx[8]={0,0,1,1,1,-1,-1,-1};
int dy[8]={1,-1,0,1,-1,0,1,-1};
int dfn[maxn],low[maxn],amt;
stack<int> s;bool isins[maxn];
int bel[maxn],scc,num[maxn],mark[maxn],val[maxn],ans;
void dfs(int u,int fa){
dfn[u]=low[u]=++amt;
s.push(u);isins[u]=1;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].v;
if(v==fa) continue;
if(!dfn[v]){
dfs(v,u);
low[u]=min(low[u],low[v]);
}
else if(isins[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
++scc;
while(s.top()!=u){
bel[s.top()]=scc;
isins[s.top()]=0,s.pop();
num[scc]++;
}
// bel[u]=scc;
// num[scc]++;
}
}
void dp(int u){
mark[u]=1;
for(int i=_head[u];i;i=_edge[i].next){
int v=_edge[i].next;
if(!mark[v]) dp(v);
val[u]=max(val[u],val[v]);
}
val[u]+=num[u];
ans=max(val[u],ans);
}
signed main(){
ios::sync_with_stdio(false);
cin >> n >> r >> c;
for(int i=1;i<=n;++i){
cin >> x[i] >> y[i] >> opt[i] ;
vis[mp(x[i],y[i])]=i;
a[x[i]].push_back(i);
b[y[i]].push_back(i);
}
for(int i=1;i<=r;++i){
int u;
for(auto x:a[i]){
if(opt[i]==1) {
u=x;
break;
}
}
for(auto v:a[i]){
add(u,v);
if(opt[v]==1) add(v,u);
}
}
for(int i=1;i<=c;++i){
int u;
for(auto x:b[i]){
if(opt[i]==2) {
u=x;
break;
}
}
for(auto v:b[i]){
add(u,v);
if(opt[v]==2) add(v,u);
}
}
for(int i=1;i<=n;++i){
if(opt[i]==3){
for(int k=0;k<8;++k){
int temp=vis[mp(x[i]+dx[k],y[i]+dy[k])];
if(temp){
add(i,temp);
}
}
}
}
for(int i=1;i<=n;++i)
if(!dfn[i]) dfs(i,0);
for(int u=1;u<=n;++u){
for(int i=head[u];i;i=edge[i].next){
if(bel[i]!=bel[u]){
_add(bel[u],bel[i]) ;
}
}
}
for(int i=1;i<=n;++i){
if(!mark[i]){
dp(i);
}
}
cout << ans << '\n' ;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 13708kb
input:
16 20 20 5 6 2 16 6 2 11 6 3 12 7 1 12 12 2 4 6 1 1 12 2 2 12 3 4 10 1 3 12 1 3 2 3 10 12 3 4 12 3 16 12 3 3 1 1 3 14 1
output:
16
result:
wrong answer 1st lines differ - expected: '12', found: '16'
Test #2:
score: 0
Runtime Error
input:
300 1000 1000 961 867 3 961 868 1 961 189 1 961 68 3 961 140 2 29 140 1 961 218 3 961 217 1 961 3 1 70 140 1 961 135 2 961 7 3 103 135 3 29 33 1 163 140 1 960 868 2 961 181 1 247 140 1 961 69 2 247 215 3 29 213 3 29 55 1 163 290 3 131 140 1 29 186 3 70 75 3 961 133 1 29 68 3 163 22 1 29 279 3 960 6 ...
output:
result:
Test #3:
score: 0
Runtime Error
input:
500 100000 100000 15043 25566 3 15044 25566 1 15042 25567 3 15043 25565 2 15042 25566 3 15043 25568 2 15042 25568 3 15041 25565 1 15044 104 2 168 25565 3 15044 491 1 15044 81 3 168 25564 1 235 104 3 15042 25565 1 15041 25566 2 15044 469 3 15044 25567 1 15044 330 1 175 25566 3 146 104 3 15043 25567 3...
output:
result:
Test #4:
score: 0
Runtime Error
input:
2500 5000 5000 3360 701 3 3361 700 3 3359 701 3 3359 700 3 3360 700 1 3361 699 2 3358 701 1 3358 700 3 3358 699 1 2447 699 2 3358 1086 3 3358 1615 1 3362 700 1 3362 1465 1 3362 1798 2 3362 699 3 3357 1087 3 3362 1261 3 3360 702 3 3361 701 2 3359 703 3 499 699 2 3358 702 3 3358 1087 3 3361 698 3 210 ...
output:
result:
Test #5:
score: 0
Runtime Error
input:
50000 5000 5000 3607 4830 3 4313 4830 1 4626 4830 3 1386 4830 3 4641 4830 1 1512 4830 3 402 4830 2 2934 4830 2 401 4831 1 4626 4584 1 4386 4831 3 4641 2551 1 3557 4830 1 2491 4830 3 2334 4584 3 3556 4831 3 4387 4831 3 3607 3496 3 4626 4601 3 4626 2217 3 3556 4830 3 3556 4786 3 4364 3496 3 402 1201 2...
output:
result:
Test #6:
score: 0
Runtime Error
input:
50000 1000000 1000000 20363 13775 3 10221 13775 3 10221 13969 3 10221 29039 3 10221 27851 3 654 13775 3 10649 29039 3 10221 22361 3 10649 8092 3 10648 8092 3 10649 24920 3 10221 25255 3 10220 25254 3 10221 17082 3 10222 13968 3 32129 27851 3 10221 23924 3 4819 29039 3 10222 13776 3 654 27930 3 10220...
output:
result:
Test #7:
score: 0
Runtime Error
input:
80000 1000000 1000000 29977 11241 3 29977 15584 3 29977 375 3 29977 3093 3 29977 31245 2 25192 15584 3 29978 31246 1 29977 23943 2 29431 31245 3 25192 2098 3 29976 374 1 7181 375 3 29977 22345 3 29979 31246 3 5598 31245 3 29977 17843 3 29431 31246 2 29976 31244 3 17885 374 3 29976 31061 3 29977 3124...
output:
result:
Test #8:
score: 0
Runtime Error
input:
100000 1000000 1000000 19362 10998 2 17887 10998 2 17887 691 2 17887 18793 2 19362 22537 1 17887 18792 1 19362 23192 2 19362 9406 2 19362 10999 1 17887 21103 1 19362 2323 2 17887 1781 2 19362 12326 1 7225 23192 1 8952 1781 1 17887 8534 1 19362 2725 2 17887 6665 1 17887 14381 1 19362 26932 1 22259 18...
output:
result:
Test #9:
score: 0
Runtime Error
input:
100000 1000000 1000000 14954 14897 3 14954 23720 2 28995 14897 2 26335 14897 3 26334 14897 2 21984 14897 3 26334 13037 3 14955 14896 3 26333 13037 2 26334 31550 2 26333 14897 3 26335 18761 3 26333 14369 3 26333 16092 3 28994 14898 3 26334 18762 3 21983 14898 3 26333 31709 1 26335 14898 3 14954 8301 ...
output:
result:
Test #10:
score: 0
Runtime Error
input:
100000 1000000 1000000 10588 4708 3 10588 28735 3 10588 28736 3 10587 4709 3 10588 20418 3 10586 4709 3 10586 17297 2 10586 26967 3 10587 17296 3 7718 17297 3 7576 17296 3 7718 3553 3 25009 17296 3 25008 17297 3 7719 3552 2 10587 14985 3 10586 24976 3 10588 16895 2 10588 11593 1 10587 14986 3 6611 3...