QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380926 | #6396. Puzzle: Kusabi | invaded | WA | 25ms | 45416kb | C++17 | 3.9kb | 2024-04-07 15:06:14 | 2024-04-07 15:06:14 |
Judging History
answer
#include<bits/stdc++.h>
#ifndef xxx
#define dbg(...) ;
#endif
using namespace std;
template<class T> ostream &operator<<(ostream &o, const vector <T> &v) { bool f=false; for(T i:v) { f?o<<' ':o; o<<(i); f=true; } return o; }
template<class T> void sort(T &v) { std::sort(v.begin(), v.end()); }
template<class T, class C> void sort(T &v, C c) { std::sort(v.begin(), v.end(), c); }
template<class T> void reverse(T &v) { std::reverse(v.begin(), v.end()); }
template<class T> bool is_sorted(T &v) { return std::is_sorted(v.begin(), v.end()); }
template<class T> inline void left_shift(T st, T ed, int shift) { std::rotate(st, st+shift, ed); }
template<class T> inline void right_shift(T st, T ed, int shift) { std::rotate(st, ed-shift, ed); }
template<class T> inline void _min(T &x, const T &y) { x>y?x=y:x; }
template<class T> inline void _max(T &x, const T &y) { x<y?x=y:x; }
istream &operator>>(istream &i, __int128_t &x) { x=0; short f=1; char c=0; while(!isdigit(c)) { if(c=='-')f=-1; c=i.get(); } while(isdigit(c))x=x*10+c-'0', c=i.get(); x*=f; return i; }
ostream &operator<<(ostream &o, __int128_t x) { if(x==0) { o<<0; return o; } bool f=false; string s; if(x<0)f=true, x=-x; while(x)s+=x%10+'0', x/=10; reverse(s); if(f)o<<'-'; o<<s; return o; }
mt19937 mt(time(0));
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
constexpr int maxn=2e5+5;
constexpr int mod=1e9+7;
constexpr int inf=0x3f3f3f3f;
constexpr ll INF=0x3f3f3f3f3f3f3f3fll;
constexpr double pi=acos(-1.0);
constexpr double eps=1e-9;
struct node
{
int id, type, dep;
node() :id(0), type(0), dep(0) {}
node(int id, int type, int dep)
{
this->id=id;
this->type=type;
this->dep=dep;
}
}nd[maxn];
vector<int>G[maxn];
vector<int>layer[maxn];
// (dep,id)
set<pii>chang[maxn], duan[maxn], tong[maxn];
void dfs(int u)
{
//dbg(u);
layer[nd[u].dep].push_back(u);
for(int v:G[u])
{
dfs(v);
}
}
int main()//MARK: main
{
#ifndef xxx
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#endif
cout<<fixed<<setprecision(10);
int n;
cin>>n;
for(int i=1; i<=n-1; i++)
{
int id, type, dep;
int p;
string s;
cin>>id>>p>>s;
if(s[0]=='C')type=1;
else if(s[0]=='D')type=2;
else if(s[0]=='T')type=3;
else type=0;
dep=nd[p].dep+1;
nd[id]=node(id, type, dep);
G[p].push_back(id);
}
dfs(1);
vector<pii>ans;
auto getans=[&]()->bool
{
for(int d=n; d>=0; d--)
{
if(layer[d].empty())continue;
dbg(d);
for(int u:layer[d])
{
auto [id, type, dep]=nd[u];
auto &C=chang[u];
auto &D=duan[u];
auto &T=tong[u];
for(int v:G[u])
{
C.insert(chang[v].begin(), chang[v].end());
D.insert(duan[v].begin(), duan[v].end());
T.insert(tong[v].begin(), tong[v].end());
}
if(type==1)C.insert({dep, u});
else if(type==2)D.insert({dep, u});
else if(type==3)T.insert({dep, u});
dbg(u, type, C.size(), D.size(), T.size());
while(!C.empty())
{
auto c=C.begin();
auto it=D.lower_bound({c->first, 0});
if(it!=D.begin())
{
it--;
dbg(c->first, it->first);
ans.push_back({c->second, it->second});
D.erase(it);
C.erase(c);
}
else
{
break;
}
}
while(!T.empty())
{
auto t=T.begin();
T.erase(t);
auto it=T.lower_bound({t->first, 0});
if(it!=T.end()&&it->first==t->first)
{
T.erase(it);
ans.push_back({t->second, it->second});
}
else
{
T.insert(make_pair(t->first, t->second));
break;
}
}
if(C.size()+D.size()+T.size()>1)
{
return false;
}
}
}
return chang[1].empty()&&duan[1].empty()&&tong[1].empty();
};
if(getans())
{
cout<<"YES"<<'\n';
for(auto [u, v]:ans)
{
cout<<u<<' '<<v<<'\n';
}
}
else
{
cout<<"NO"<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 43620kb
input:
8 2 1 - 3 1 - 4 2 Tong 5 2 Tong 6 3 Duan 7 3 - 8 7 Chang
output:
YES 4 5 8 6
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 43492kb
input:
10 2 1 Duan 3 2 Duan 4 2 - 5 4 Chang 6 2 Chang 7 1 Duan 8 6 Tong 9 6 Tong 10 3 Chang
output:
YES 10 3 8 9 6 2 5 7
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 8ms
memory: 43536kb
input:
2 2 1 Tong
output:
NO
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 25ms
memory: 45416kb
input:
100000 2 1 Duan 3 1 Duan 4 3 - 5 4 Duan 6 3 - 7 4 Duan 8 4 - 9 8 - 10 7 Duan 11 9 - 12 7 Duan 13 7 Duan 14 8 Duan 15 13 - 16 10 Duan 17 11 Duan 18 12 - 19 1 Duan 20 5 Duan 21 4 Duan 22 14 Duan 23 16 - 24 22 Duan 25 16 Duan 26 13 - 27 13 - 28 17 - 29 5 Duan 30 22 - 31 23 - 32 9 Duan 33 5 - 34 30 Duan...
output:
NO
result:
wrong answer Jury has answer but participant has not.