QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#198310 | #3614. Math Trade | Zhou_JK | WA | 1ms | 3440kb | C++23 | 1.1kb | 2023-10-03 12:42:12 | 2023-10-03 12:42:12 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
const int N=105;
int n;
int tot;
map<string,int>id;
vector<int>G[N*2];
int deg[N*2];
bool vis[N*2];
int cnt;
bool flag;
void dfs(int u)
{
vis[u]=true;
cnt++;
for(int v:G[u])
{
if(deg[v]!=1)
{
flag=false;
return;
}
if(vis[v]) continue;
dfs(v);
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++)
{
string name,s,t;
cin>>name>>s>>t;
if(!id.count(s)) id[s]=++tot;
if(!id.count(t)) id[t]=++tot;
G[id[s]].emplace_back(id[t]);
G[id[t]].emplace_back(id[s]);
deg[id[t]]++;
}
int ans=0;
for(int i=1;i<=tot;i++)
if(!vis[i])
{
flag=true;
cnt=0;
dfs(i);
if(flag) ans=max(ans,cnt);
}
if(ans==0) cout<<"No trades possible";
else cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3420kb
input:
4 Sally Clock Doll Steve Doll Painting Carlos Painting Clock Maria Candlestick Vase
output:
3
result:
ok single line: '3'
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3440kb
input:
4 Abby Bottlecap Card Bob Card Spoon Chris Spoon Chair Dan Pencil Pen
output:
2
result:
wrong answer 1st lines differ - expected: 'No trades possible', found: '2'