답안 #367459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
367459	2021-02-17T12:34:56 Z	MilosMilutinovic	슈퍼트리 잇기 (IOI20_supertrees)	C++14	21 / 100	308 ms	31980 KB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define pb push_back
const int N=1050;
vector<int> E[N];
vector<vector<int>> p,ans(N,vector<int>(N,0));
void AddEdge(int u,int v){E[u].pb(v);E[v].pb(u);}
bool was[N];
vector<int> euler;
void DFS1(int u){
    was[u]=true;
    euler.pb(u);
    for(int e:E[u])if(!was[e]&&p[u][e]==1)DFS1(e);
}
void DFS2(int u){
    was[u]=true;
    euler.pb(u);
    for(int e:E[u])if(!was[e]&&p[u][e]==2)DFS2(e);
}
int construct(vector<vector<int>> P){
    int n=(int)P.size();p=P;
    ans.resize(n);
    for(int i=0;i<n;i++)ans[i].resize(n);
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(p[i][j]==3)return 0;
    for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)if(p[i][j]>0)AddEdge(i,j);
    for(int i=0;i<n;i++)if(!was[i]){
        DFS1(i);
        for(int x:euler)for(int y:euler)if(x!=y&&p[x][y]==0)return 0;
        for(int i=1;i<(int)euler.size();i++){
            int from=euler[i],to=euler[i-1];
            ans[from][to]=ans[to][from]=1;
        }
        euler.clear();
    }
    memset(was,false,sizeof(was));
    for(int i=0;i<n;i++)if(!was[i]){
        DFS2(i);
        if((int)euler.size()==1){
            euler.clear();
            continue;
        }
        if((int)euler.size()==2)return 0;
        for(int x:euler)for(int y:euler)if(x!=y&&p[x][y]==0)return 0;
        for(int i=0;i<(int)euler.size();i++){
            int from=euler[i],to=euler[i-1];
            ans[from][to]=ans[to][from]=1;
        }
        int from=euler[0],to=euler.back();
        ans[from][to]=ans[to][from]=1;
        euler.clear();
    }
    build(ans);
    return 1;
}

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4716 KB	Output is correct
2	Correct	3 ms	4716 KB	Output is correct
3	Correct	3 ms	4716 KB	Output is correct
4	Correct	3 ms	4716 KB	Output is correct
5	Correct	3 ms	4716 KB	Output is correct
6	Correct	13 ms	5356 KB	Output is correct
7	Correct	284 ms	31980 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4716 KB	Output is correct
2	Correct	3 ms	4716 KB	Output is correct
3	Correct	3 ms	4716 KB	Output is correct
4	Correct	3 ms	4716 KB	Output is correct
5	Correct	3 ms	4716 KB	Output is correct
6	Correct	13 ms	5356 KB	Output is correct
7	Correct	284 ms	31980 KB	Output is correct
8	Correct	3 ms	4864 KB	Output is correct
9	Correct	3 ms	4716 KB	Output is correct
10	Correct	3 ms	4716 KB	Output is correct
11	Correct	3 ms	4716 KB	Output is correct
12	Correct	13 ms	5356 KB	Output is correct
13	Correct	270 ms	27756 KB	Output is correct
14	Correct	3 ms	4716 KB	Output is correct
15	Correct	3 ms	4716 KB	Output is correct
16	Correct	10 ms	5228 KB	Output is correct
17	Correct	110 ms	20860 KB	Output is correct
18	Correct	3 ms	4716 KB	Output is correct
19	Correct	3 ms	4716 KB	Output is correct
20	Correct	67 ms	8684 KB	Output is correct
21	Correct	254 ms	28524 KB	Output is correct
22	Correct	249 ms	28008 KB	Output is correct
23	Correct	308 ms	30060 KB	Output is correct
24	Correct	248 ms	27756 KB	Output is correct
25	Correct	107 ms	18412 KB	Output is correct
26	Correct	102 ms	18028 KB	Output is correct
27	Correct	256 ms	31084 KB	Output is correct
28	Correct	265 ms	28012 KB	Output is correct

Subtask #3
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4716 KB	Output is correct
2	Correct	4 ms	4716 KB	Output is correct
3	Correct	3 ms	4716 KB	Output is correct
4	Correct	3 ms	4716 KB	Output is correct
5	Incorrect	3 ms	4716 KB	b[0][0] is not 0
6	Halted	0 ms	0 KB	-

Subtask #4
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4716 KB	Output is correct
2	Incorrect	4 ms	4716 KB	b[0][0] is not 0
3	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4716 KB	Output is correct
2	Correct	3 ms	4716 KB	Output is correct
3	Correct	3 ms	4716 KB	Output is correct
4	Correct	3 ms	4716 KB	Output is correct
5	Correct	3 ms	4716 KB	Output is correct
6	Correct	13 ms	5356 KB	Output is correct
7	Correct	284 ms	31980 KB	Output is correct
8	Correct	3 ms	4864 KB	Output is correct
9	Correct	3 ms	4716 KB	Output is correct
10	Correct	3 ms	4716 KB	Output is correct
11	Correct	3 ms	4716 KB	Output is correct
12	Correct	13 ms	5356 KB	Output is correct
13	Correct	270 ms	27756 KB	Output is correct
14	Correct	3 ms	4716 KB	Output is correct
15	Correct	3 ms	4716 KB	Output is correct
16	Correct	10 ms	5228 KB	Output is correct
17	Correct	110 ms	20860 KB	Output is correct
18	Correct	3 ms	4716 KB	Output is correct
19	Correct	3 ms	4716 KB	Output is correct
20	Correct	67 ms	8684 KB	Output is correct
21	Correct	254 ms	28524 KB	Output is correct
22	Correct	249 ms	28008 KB	Output is correct
23	Correct	308 ms	30060 KB	Output is correct
24	Correct	248 ms	27756 KB	Output is correct
25	Correct	107 ms	18412 KB	Output is correct
26	Correct	102 ms	18028 KB	Output is correct
27	Correct	256 ms	31084 KB	Output is correct
28	Correct	265 ms	28012 KB	Output is correct
29	Correct	3 ms	4716 KB	Output is correct
30	Correct	4 ms	4716 KB	Output is correct
31	Correct	3 ms	4716 KB	Output is correct
32	Correct	3 ms	4716 KB	Output is correct
33	Incorrect	3 ms	4716 KB	b[0][0] is not 0
34	Halted	0 ms	0 KB	-

Subtask #6
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4716 KB	Output is correct
2	Correct	3 ms	4716 KB	Output is correct
3	Correct	3 ms	4716 KB	Output is correct
4	Correct	3 ms	4716 KB	Output is correct
5	Correct	3 ms	4716 KB	Output is correct
6	Correct	13 ms	5356 KB	Output is correct
7	Correct	284 ms	31980 KB	Output is correct
8	Correct	3 ms	4864 KB	Output is correct
9	Correct	3 ms	4716 KB	Output is correct
10	Correct	3 ms	4716 KB	Output is correct
11	Correct	3 ms	4716 KB	Output is correct
12	Correct	13 ms	5356 KB	Output is correct
13	Correct	270 ms	27756 KB	Output is correct
14	Correct	3 ms	4716 KB	Output is correct
15	Correct	3 ms	4716 KB	Output is correct
16	Correct	10 ms	5228 KB	Output is correct
17	Correct	110 ms	20860 KB	Output is correct
18	Correct	3 ms	4716 KB	Output is correct
19	Correct	3 ms	4716 KB	Output is correct
20	Correct	67 ms	8684 KB	Output is correct
21	Correct	254 ms	28524 KB	Output is correct
22	Correct	249 ms	28008 KB	Output is correct
23	Correct	308 ms	30060 KB	Output is correct
24	Correct	248 ms	27756 KB	Output is correct
25	Correct	107 ms	18412 KB	Output is correct
26	Correct	102 ms	18028 KB	Output is correct
27	Correct	256 ms	31084 KB	Output is correct
28	Correct	265 ms	28012 KB	Output is correct
29	Correct	3 ms	4716 KB	Output is correct
30	Correct	4 ms	4716 KB	Output is correct
31	Correct	3 ms	4716 KB	Output is correct
32	Correct	3 ms	4716 KB	Output is correct
33	Incorrect	3 ms	4716 KB	b[0][0] is not 0
34	Halted	0 ms	0 KB	-

답안 #367459

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 19.0

Subtask #4 0 / 35.0

Subtask #5 0 / 21.0

Subtask #6 0 / 4.0

Subtask #1
11.0 / 11.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 19.0

Subtask #4
0 / 35.0

Subtask #5
0 / 21.0

Subtask #6
0 / 4.0