QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#325980#6315. 填数游戏littlecat#Compile Error//C++146.8kb2024-02-12 06:27:582024-07-04 03:23:49

Judging History

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

  • [2024-07-04 03:23:49]
  • 评测
查看
  • [2024-02-12 06:27:58]
  • 提交

answer

// #define DEBUG
int TIMER=20;
#define TIME if(!TIMER--)exit(0);
#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
using namespace std; const int mx=1000000; typedef pair<int,int> pi;
#define pb push_back
#define f first
#define s second

pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
pi e[mx],es[mx]; vector<int> adj[mx]; //graph

int cntE,cntV; bool vis[mx]; //components
void dfs1(int c)
{
    if(vis[c]) return; cntV++, cntE+=adj[c].size(), vis[c]=1;
    for(int t:adj[c]) dfs1(e[t].f+e[t].s-c);
}

bool cycle[mx],cycledone; int cpar[mx],rt;
void dfs2(int c, int p)
{
    cpar[c]=p; for(int t:adj[c])
    {
        int k=e[t].f+e[t].s-c; if(k==p) continue; if(cpar[k]==-1) dfs2(k,c); else if(!cycledone)
        {rt=c,cycledone=1; while(1) {cycle[rt]=1; if(rt==k) break; rt=cpar[rt];}}
    }
}
bool vis3[mx]; int cnt3;
void dfs3(int c, int p)
{
    if(vis3[c]) return; vis3[c]=1; for(int t:adj[c])
    {
        int k=e[t].f+e[t].s-c; if(k==p) continue; dfs3(k,c);
        if(!cycle[k]) cnt3+=k==es[t].f||k==es[t].s;
    }
}
vector<int> cv, cn;
void getcycle(int c)
{
    cn.pb(c); if(c==rt&&!cv.empty()) return; for(int t:adj[c])
    {
        int k=e[t].f+e[t].s-c;
        if(cycle[k]&&!(!cv.empty()&&t==cv.back())) cv.pb(t), getcycle(k);
    }
}

int solve()
{
#ifdef DEBUG
cout<<"Start\n"<<flush;
#endif
    //note: swap m/n
    int m,n,a,b,ans=0; cin>>m>>n;
    for(int i=0; i<n; i++) adj0[i].clear(),adj[i].clear(), vis[i]=vis3[i]=0, cycle[i]=0, cpar[i]=-1;
    for(int i=0; i<m; i++) edge[i]=1;
    //input and delete |T|=1
{
    for(int i=0; i<m; i++) {int c; cin>>c>>a; if(c==2) cin>>b; else b=0; s1[i]=pi(a-1,b-1);}
    for(int i=0; i<m; i++) {int c; cin>>c>>a; if(c==2) cin>>b; else b=0; s2[i]=pi(a-1,b-1);
        sz1[i]=2-c, adj0[a-1].pb(i); if(c==2) adj0[b-1].pb(i);}
    vector<int> rm; for(int i=0; i<m; i++) if(sz1[i]) rm.pb(i);
    while(!rm.empty())
    {
        int i=rm.back(); rm.pop_back(); if(!edge[i]) continue; if(s2[i].f==-1) return -1;
        ans+=s2[i].f==s1[i].f||s2[i].f==s1[i].s;
#ifdef DEBUG
cout<<"Assign "<<i<<' '<<s2[i].f<<" ("<<s2[i].s<<")\n";
#endif
        edge[i]=0; for(int j:adj0[s2[i].f]) {if(s2[j].f==s2[i].f) s2[j].f=s2[j].s; s2[j].s=-1, rm.pb(j);}
    }
    int E=0;
    for(int i=0; i<m; i++) if(edge[i]) adj[s2[i].f].pb(E),adj[s2[i].s].pb(E), e[E]=s2[i],es[E++]=s1[i];
    m=E;
}
#ifdef DEBUG
cout<<m<<' '<<ans<<'\n'; for(int i=0; i<m; i++) cout<<e[i].f<<' '<<e[i].s<<' '<<es[i].f<<' '<<es[i].s<<'\n';
for(int i=0; i<n; i++) {cout<<i<<'\t'; for(int t:adj[i]) cout<<t<<' '; cout<<'\n';} cout<<flush;
#endif
for(int i=0; i<n; i++) if(!vis[i])
{
    //count edges
    cntE=cntV=0, dfs1(i); if(cntE>2*cntV) return -1;
    if(cntE==2*cntV)
    {
        //cycle with trees: explicit formula
        cycledone=0, dfs2(i,-2);
        cnt3=0, dfs3(rt,-1), ans+=cnt3;
        cv.clear(),cn.clear(), getcycle(rt);
        int A=0,B=0,C=0; for(int i=0; i<cv.size(); i++)
        {
            bool x1=cn[i]==es[cv[i]].f||cn[i]==es[cv[i]].s, x2=cn[i+1]==es[cv[i]].f||cn[i+1]==es[cv[i]].s;
            if(x1&&x2) C++; else if(x1) A++; else if(x2) B++;
        }
        ans+=min(min(A,B)+C,(A+B+C)/2);
    }
    else
    {
        //tree with variable root: dp
        ;
    }
}
    return ans;
}
int main()
{
    int T; cin.sync_with_stdio(0),cin.tie(0),cin>>T; while(T--) cout<<solve()<<'\n';
}// #define DEBUG
int TIMER=20;
#define TIME if(!TIMER--)exit(0);
#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
using namespace std; const int mx=1000000; typedef pair<int,int> pi;
#define pb push_back
#define f first
#define s second

pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
pi e[mx],es[mx]; vector<int> adj[mx]; //graph

int cntE,cntV; bool vis[mx]; //components
void dfs1(int c)
{
    if(vis[c]) return; cntV++, cntE+=adj[c].size(), vis[c]=1;
    for(int t:adj[c]) dfs1(e[t].f+e[t].s-c);
}

bool cycle[mx],cycledone; int cpar[mx],rt;
void dfs2(int c, int p)
{
    cpar[c]=p; for(int t:adj[c])
    {
        int k=e[t].f+e[t].s-c; if(k==p) continue; if(cpar[k]==-1) dfs2(k,c); else if(!cycledone)
        {rt=c,cycledone=1; while(1) {cycle[rt]=1; if(rt==k) break; rt=cpar[rt];}}
    }
}
bool vis3[mx]; int cnt3;
void dfs3(int c, int p)
{
    if(vis3[c]) return; vis3[c]=1; for(int t:adj[c])
    {
        int k=e[t].f+e[t].s-c; if(k==p) continue; dfs3(k,c);
        if(!cycle[k]) cnt3+=k==es[t].f||k==es[t].s;
    }
}
vector<int> cv, cn;
void getcycle(int c)
{
    cn.pb(c); if(c==rt&&!cv.empty()) return; for(int t:adj[c])
    {
        int k=e[t].f+e[t].s-c;
        if(cycle[k]&&!(!cv.empty()&&t==cv.back())) cv.pb(t), getcycle(k);
    }
}

int solve()
{
#ifdef DEBUG
cout<<"Start\n"<<flush;
#endif
    //note: swap m/n
    int m,n,a,b,ans=0; cin>>m>>n;
    for(int i=0; i<n; i++) adj0[i].clear(),adj[i].clear(), vis[i]=vis3[i]=0, cycle[i]=0, cpar[i]=-1;
    for(int i=0; i<m; i++) edge[i]=1;
    //input and delete |T|=1
{
    for(int i=0; i<m; i++) {int c; cin>>c>>a; if(c==2) cin>>b; else b=0; s1[i]=pi(a-1,b-1);}
    for(int i=0; i<m; i++) {int c; cin>>c>>a; if(c==2) cin>>b; else b=0; s2[i]=pi(a-1,b-1);
        sz1[i]=2-c, adj0[a-1].pb(i); if(c==2) adj0[b-1].pb(i);}
    vector<int> rm; for(int i=0; i<m; i++) if(sz1[i]) rm.pb(i);
    while(!rm.empty())
    {
        int i=rm.back(); rm.pop_back(); if(!edge[i]) continue; if(s2[i].f==-1) return -1;
        ans+=s2[i].f==s1[i].f||s2[i].f==s1[i].s;
#ifdef DEBUG
cout<<"Assign "<<i<<' '<<s2[i].f<<" ("<<s2[i].s<<")\n";
#endif
        edge[i]=0; for(int j:adj0[s2[i].f]) {if(s2[j].f==s2[i].f) s2[j].f=s2[j].s; s2[j].s=-1, rm.pb(j);}
    }
    int E=0;
    for(int i=0; i<m; i++) if(edge[i]) adj[s2[i].f].pb(E),adj[s2[i].s].pb(E), e[E]=s2[i],es[E++]=s1[i];
    m=E;
}
#ifdef DEBUG
cout<<m<<' '<<ans<<'\n'; for(int i=0; i<m; i++) cout<<e[i].f<<' '<<e[i].s<<' '<<es[i].f<<' '<<es[i].s<<'\n';
for(int i=0; i<n; i++) {cout<<i<<'\t'; for(int t:adj[i]) cout<<t<<' '; cout<<'\n';} cout<<flush;
#endif
for(int i=0; i<n; i++) if(!vis[i])
{
    //count edges
    cntE=cntV=0, dfs1(i); if(cntE>2*cntV) return -1;
    if(cntE==2*cntV)
    {
        //cycle with trees: explicit formula
        cycledone=0, dfs2(i,-2);
        cnt3=0, dfs3(rt,-1), ans+=cnt3;
        cv.clear(),cn.clear(), getcycle(rt);
        int A=0,B=0,C=0; for(int i=0; i<cv.size(); i++)
        {
            bool x1=cn[i]==es[cv[i]].f||cn[i]==es[cv[i]].s, x2=cn[i+1]==es[cv[i]].f||cn[i+1]==es[cv[i]].s;
            if(x1&&x2) C++; else if(x1) A++; else if(x2) B++;
        }
        ans+=min(min(A,B)+C,(A+B+C)/2);
    }
    else
    {
        //tree with variable root: dp
        ;
    }
}
    return ans;
}
int main()
{
    int T; cin.sync_with_stdio(0),cin.tie(0),cin>>T; while(T--) cout<<solve()<<'\n';
}
源文件, 语言: C++14

詳細信息 

answer.code:111:5: error: redefinition of ‘int TIMER’
  111 | int TIMER=20;
      |     ^~~~~
answer.code:2:5: note: ‘int TIMER’ previously defined here
    2 | int TIMER=20;
      |     ^~~~~
answer.code:116:32: error: redefinition of ‘const int mx’
  116 | using namespace std; const int mx=1000000; typedef pair<int,int> pi;
      |                                ^~
answer.code:7:32: note: ‘const int mx’ previously defined here
    7 | using namespace std; const int mx=1000000; typedef pair<int,int> pi;
      |                                ^~
answer.code:121:4: error: redefinition of ‘pi s1 [1000000]’
  121 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |    ^~
answer.code:12:4: note: ‘pi s1 [1000000]’ previously defined here
   12 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |    ^~
answer.code:121:11: error: redefinition of ‘pi s2 [1000000]’
  121 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |           ^~
answer.code:12:11: note: ‘pi s2 [1000000]’ previously defined here
   12 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |           ^~
answer.code:121:24: error: redefinition of ‘bool sz1 [1000000]’
  121 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |                        ^~~
answer.code:12:24: note: ‘bool sz1 [1000000]’ previously declared here
   12 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |                        ^~~
answer.code:121:32: error: redefinition of ‘bool edge [1000000]’
  121 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |                                ^~~~
answer.code:12:32: note: ‘bool edge [1000000]’ previously declared here
   12 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |                                ^~~~
answer.code:121:54: error: redefinition of ‘std::vector<int> adj0 [1000000]’
  121 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |                                                      ^~~~
answer.code:12:54: note: ‘std::vector<int> adj0 [1000000]’ previously declared here
   12 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |                                                      ^~~~
answer.code:122:4: error: redefinition of ‘pi e [1000000]’
  122 | pi e[mx],es[mx]; vector<int> adj[mx]; //graph
      |    ^
answer.code:13:4: note: ‘pi e [1000000]’ previously defined here
   13 | pi e[mx],es[mx]; vector<int> adj[mx]; //graph
      |    ^
answer.code:122:10: error: redefinition of ‘pi es [1000000]’
  122 | pi e[mx],es[mx]; vector<int> adj[mx]; //graph
      |          ^~
answer.code:13:10: note: ‘pi es [1000000]’ previously defined here
   13 | pi e[mx],es[mx]; vector<int> adj[mx]; //graph
      |          ^~
answer.code:122:30: error: redefinition of ‘std::vector<int> adj [1000000]’
  122 | pi e[mx],es[mx]; vector<int> adj[mx]; //graph
      |                              ^~~
answer.code:13:30: note: ‘std::vector<int> adj [1000000]’ previously declared here
   13 | pi e[mx],es[mx]; vector<int> adj[mx]; //graph
      |                              ^~~
answer.code:124:5: error: redefinition of ‘int cntE’
  124 | int cntE,cntV; bool vis[mx]; //components
      |     ^~~~
answer.code:15:5: note: ‘int cntE’ previously declared here
   15 | int cntE,cntV; bool vis[mx]; //components
      |     ^~~~
answer.code:124:10: error: redefinition of ‘int cntV’
  124 | int cntE,cntV; bool vis[mx]; //components
      |          ^~~~
answer.code:15:10: note: ‘int cntV’ previously declared here
   15 | int cntE,cntV; bool vis[mx]; //components
      |          ^~~~
answer.code:124:21: error: redefinition of ‘bool vis [1000000]’
  124 | int cntE,cntV; bool vis[mx]; //components
      |                     ^~~
answer.code:15:21: note: ‘bool vis [1000000]’ previously declared here
   15 | int cntE,cntV; bool vis[mx]; //components
      |                     ^~~
answer.code:125:6: error: redefinition of ‘void dfs1(int)’
  125 | void dfs1(int c)
      |      ^~~~
answer.code:16:6: note: ‘void dfs1(int)’ previously defined here
   16 | void dfs1(int c)
      |      ^~~~
answer.code:131:6: error: redefinition of ‘bool cycle [1000000]’
  131 | bool cycle[mx],cycledone; int cpar[mx],rt;
      |      ^~~~~
answer.code:22:6: note: ‘bool cycle [1000000]’ previously declared here
   22 | bool cycle[mx],cycledone; int cpar[mx],rt;
      |      ^~~~~
answer.code:131:16: error: redefinition of ‘bool cycledone’
  131 | bool cycle[mx],cycledone; int cpar[mx],rt;
      |                ^~~~~~~~~
answer.code:22:16: note: ‘bool cycledone’ previously declared here
   22 | bool cycle[mx],cycledone; int cpar[mx],rt;
      |                ^~~~~~~~~
answer.code:131:31: error: redefinition of ‘int cpar [1000000]’
  131 |...
English 繁體中文 简体中文

伺服器時間: 2024-12-12 00:43:39 | 開源專案