이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DIMN 200010
using namespace std;
int sol , x[DIMN];
int lnt,nrc;
int d[DIMN],l[DIMN],poz[DIMN],up[DIMN],f[DIMN],val[DIMN],lvl[DIMN];
int cnt[DIMN];
vector <int> v[DIMN],w[DIMN];
struct segm{
int par, imp , lzy;
};
vector <segm> aint[DIMN];
void precalc (int nod){
int i,vecin;
d[nod]=1;
f[nod]=1;
cnt[nod] = 0;
if (v[nod].size() == 1)
cnt[nod] = 1;
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (!f[vecin]){
lvl[vecin]=1+lvl[nod];
precalc (vecin);
d[nod]+=d[vecin];
cnt[nod] += cnt[vecin];
}
}
}
void dfs_lant(int nod,int tata){
int i,vecin,ok=0,maxi,fiu;
maxi=0;
fiu=0;
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (vecin!=tata){
ok=1;
dfs_lant(vecin,nod);
if (d[vecin]>maxi){
maxi=d[vecin];
fiu=vecin;
}
}
}
if (!ok){ /// frunza
lnt++;
l[nod]=lnt; /// lantul din care apartine
w[lnt].push_back(nod);
}else { /// unim cu poz
w[l[fiu]].push_back(nod);
l[nod]=l[fiu];
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (vecin!=tata && vecin!=fiu)
up[l[vecin]]=nod; /// din lantul vecinului trecem in lantul nodului
}
}
}
void update_lazy (int lant , int p , int st , int dr){
if (aint[lant][p].lzy){
aint[lant][p].lzy = 0;
swap(aint[lant][p].par , aint[lant][p].imp);
if (st != dr){
aint[lant][2 * p].lzy = 1 - aint[lant][2 * p].lzy;
aint[lant][2 * p + 1].lzy = 1 - aint[lant][2 * p + 1].lzy;
}
}
}
void build_aint (int lant,int p,int st,int dr){
int mid;
if (st==dr){
aint[lant][p].par++;
return;
}
mid=(st+dr)/2;
build_aint(lant,2*p,st,mid);
build_aint(lant,2*p+1,mid+1,dr);
aint[lant][p].par = aint[lant][2*p].par + aint[lant][2*p+1].par;
aint[lant][p].imp = aint[lant][2*p].imp + aint[lant][2*p+1].imp;
}
void update_aint (int lant,int p,int st,int dr,int px , int py){
int mid;
update_lazy(lant , p , st , dr);
if (px <= st && dr <= py){ /// interval ok
/// in tot intervalul asta are loc schimbul de stari
aint[lant][p].lzy = 1 - aint[lant][p].lzy;
update_lazy(lant , p , st , dr);
return;
}
mid=(st+dr)/2;
if (px<=mid)
update_aint(lant,2*p,st,mid,px , py);
if (mid + 1 <= py)
update_aint(lant,2*p+1,mid+1,dr,px , py);
update_lazy(lant , 2 * p , st , mid);
update_lazy(lant , 2 * p + 1 , mid + 1 , dr);
aint[lant][p].par = aint[lant][2*p].par + aint[lant][2*p+1].par;
aint[lant][p].imp = aint[lant][2*p].imp + aint[lant][2*p+1].imp;
}
void update (int x,int y){
/// pe lantul de la x la y, fiecare nod isi schimba starea proprie
/// asa ca la un nod de pe lant, scazi
if (l[x]!=l[y]){ /// avansam
update(up[l[x]],y);
update_aint(l[x],1,0,w[l[x]].size()-1,0,poz[x]);
}
else{
update_aint(l[x],1,0,w[l[x]].size()-1,min(poz[x],poz[y]),max(poz[x],poz[y]));
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , q , xx , y , d , i , root , frnz = 0 , p , vecin;
fscanf (fin,"%d%d",&n,&q);
for (i = 1 ; i < n ; i++){
fscanf (fin,"%d%d",&xx,&y);
v[xx].push_back(y);
v[y].push_back(xx);
}
for (i = 1 ; i <= n ; i++){
if (v[i].size() > 1){
root = i;
break;
}
}
precalc(root);
dfs_lant(root , 0);
for (i=1;i<=lnt;i++){
reverse(w[i].begin(),w[i].end());
p=0;
for (vector <int> :: iterator j=w[i].begin();j!=w[i].end();j++){
/// pozitia lui din lantul curent
vecin=*j;
poz[vecin]=p;
p++;
}
}
for (i=1;i<=lnt;i++){
aint[i].resize(w[i].size()*5);
nrc=0;
build_aint(i,1,0,w[i].size()-1);
}
for (i = 1 ; i <= n ; i++){
if (v[i].size() == 1){
frnz++;
update(i , root);
}
}
for (;q;q--){
fscanf (fin,"%d",&d);
for (i = 1 ; i <= d ; i++){
fscanf (fin,"%d",&x[i]);
update (x[i] , root);
if (v[x[i]].size() != 1)
frnz++;
}
sol = 0;
if (frnz % 2)
fprintf (fout,"-1\n");
else {
sol = n + d - 1;
for (i = 1 ; i <= lnt ; i++){
update_lazy(i , 1 , 0 , w[i].size() - 1);
sol += aint[i][1].par;
}
fprintf (fout,"%d\n" , sol - 1);
}
for (i = 1 ; i <= d ; i++){
if (v[x[i]].size() != 1)
frnz--;
update (x[i] , root);
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
cleaning.cpp: In function 'void precalc(int)':
cleaning.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for (i=0;i<v[nod].size();i++){
| ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'void dfs_lant(int, int)':
cleaning.cpp:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (i=0;i<v[nod].size();i++){
| ~^~~~~~~~~~~~~~
cleaning.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (i=0;i<v[nod].size();i++){
| ~^~~~~~~~~~~~~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:137:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
137 | fscanf (fin,"%d%d",&n,&q);
| ~~~~~~~^~~~~~~~~~~~~~~~~~
cleaning.cpp:139:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
139 | fscanf (fin,"%d%d",&xx,&y);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
cleaning.cpp:178:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
178 | fscanf (fin,"%d",&d);
| ~~~~~~~^~~~~~~~~~~~~
cleaning.cpp:181:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
181 | fscanf (fin,"%d",&x[i]);
| ~~~~~~~^~~~~~~~~~~~~~~~
cleaning.cpp:204:20: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
204 | update (x[i] , root);
| ~~~~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |